为什么开unsigned long long就一直wa???
把第七行的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,有没有大佬告诉我为什么………