关于ull
查看原帖
关于ull
728746
LittleDrinks楼主2023/4/15 11:08

为什么开unsigned long long就一直wa???

开ull

开ll

把第七行的long long换成unsigned long long就全wa

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e6+5;
int n, q[MAXN], head=1, tail=1;
long long x[MAXN], p[MAXN], c[MAXN], sp[MAXN], sxp[MAXN], f[MAXN], ans=LLONG_MAX;

/*
设从j+1至i划为一组,则在i处建仓库花费c[i],运费sum{ (x[i]-x[k])*p[k] }
即:f[i] = min{ f[j] + sum{(x[i]-x[k])*p[k]} + c[i] }, j<k<=i
设sp[]是p[]的前缀和数组,sxp[]是x[]*p[]的前缀和数组
运费可化简为:sum{ x[i]*(sp[i]-sp[j])-(sxp[i]-sxp[j]) }
方程化为:(f[j]+sxp[j]) - x[i]*sp[j] + (x[i]*sp[i]-sxp[i]+c[i])

斜率优化:
x(j) (sp[j])
y(j) (f[j]+sxp[j])
k(i) (x[i])
*/

#define x(j) (sp[j])
#define y(j) (f[j]+sxp[j])
#define k(i) (x[i])
#define IC(i,j) (y(j)-k(i)*x(j))

bool check(int i, int j, int k)
{
    return (
        (y(k)-y(j))*(x(j)-x(i))
        <= (y(j)-y(i))*(x(k)-x(j))
    );
}

int main()
{
    // freopen("P2120_03.in", "r", stdin);
    cin.tie(nullptr) -> sync_with_stdio(false);

    // I.N.
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> p[i] >> c[i];
        sp[i]  = sp[i-1]  + p[i];
        sxp[i] = sxp[i-1] + x[i]*p[i];
    }

    // D.P.
    for (int i = 1; i <= n; ++i) {
        while ( (head<tail) && ( IC(i,q[head]) >= IC(i,q[head+1])) ) { ++head; }
        int j = q[head];
        f[i] = f[j] + c[i] + x[i]*(sp[i]-sp[j]) - (sxp[i]-sxp[j]);
        while ( (head<tail) && ( check(q[tail-1], q[tail], i)) ) { --tail; }
        q[++tail] = i;
    }

    // 逆序扫描,如果末尾p=0,那么不用建仓库,答案不是f[n]
    for (int i = n; i; --i) {
        ans = min(ans, f[i]);
        if (p[i]) { break; }
    }

    // E.D.
    cout << ans << endl;
    return 0;
}

数据范围看错调了我3h,有没有大佬告诉我为什么………

2023/4/15 11:08
加载中...