首页 > 代码库 > BZOJ1096 [ZJOI2007]仓库建设

BZOJ1096 [ZJOI2007]仓库建设

2024-07-26 15:13:18   220人阅读

蒟蒻就写一下简单题吧。。。

此题很容易写出dp的方程：

令f[i]表示i号点要建仓库的话最小总费用，则

f[i] = min(f[j]  + (x[i] - x[j + 1]) * p[i + 1] + (x[i] - x[j + 2])* p[i + 2] + ... + (x[i] - x[i]) * p[i]) + c[i]

然后把min里面的东西展开再合并，并且令

sp[i] = p[1] + p[2] + ... + p[i]

s[i] = x[1] * p[1] + x[2] * p[2] + ... + x[i] * p[i]

那么：

f[i] = min(f[j] + s[j] - x[i] * sp[j]) + c[i] + sp[i] * x[i] - s[i];

然后前面的min里的式子可以斜率优化掉，就做完了。（我好像会自己推了?进步+1^_^）

 

 

 1 #include <cstdlib> 2 #include <cstdio> 3 #include <iostream> 4   5 using namespace std; 6   7 long long q[1200000], s[1200000], sp[1200000], f[1200000], g[1200000]; 8 long long x; 9 int l = 1, r = 1, n;10  11 inline bool pop_head(){12     int a = q[l], b = q[l + 1];13     return (long long) g[b] - g[a] < (long long)x * (sp[b] - sp[a]);14 }15  16 inline bool pop_tail(int i){17     int a = q[r - 1], b = q[r];18     return (long long) (g[b] - g[a]) * (sp[i] - sp[b]) >= (long long) (g[i] - g[b]) * (sp[b] - sp[a]);19 }20  21 int main(){22     scanf("%d\n", &n);23     long long p, c;24     q[1] = 0;25     int j;26     for (int i = 1; i <= n; ++i){27         scanf("%lld %lld %lld\n", &x, &p, &c);28         sp[i] = sp[i - 1] + p;29         s[i] = s[i - 1] + x * p;30         while (l < r && pop_head()) ++l;31         j = q[l];32         f[i] = g[j] - x * sp[j] + c + sp[i] * x - s[i];33         g[i] = f[i] + s[i];34         while (l < r && pop_tail(i)) --r;35         q[++r] = i;36     }37     printf("%lld\n", f[n]);38     return 0;39 }
View Code

(p.s. 沙茶的我把q写成g，结果WA了两次。。。)

BZOJ1096 [ZJOI2007]仓库建设


联系
我们