1.BZOJ 1096 仓库建设
题目链接
http://www.lydsy.com/JudgeOnline/problem.php?id=1096
思路
令
f[i]=[1,i]
区间，在第i个工厂建立仓库，所需最少总花费。DP方程显然
f[i]=min1≤j<i{f[j]+w[j,i]}+C[i]
其中
w[j,i]=P[j+1](X[i]−X[j+1])+P[j+2](X[i]−X[j+2])+...+P[i](X[i]−X[i])
w[j,i]=X[i]∑t=j+1iP[t]−∑t=j+1iP[t]X[t]
令
sumP[i]=∑it=1P[t],sum[i]=∑it=1P[t]X[t]
设对于
f[i]
而言，
x>y
且
f[x]
比
f[y]
更优，则
f[x]+w[x,i]<f[y]+w[y,i]
f[x]−X[i]sumP[x]+sum[x]<f[y]−X[i]sumP[y]+sum[y]
(f[x]+sum[x])−(f[y]+sum[y])<X[i](sumP[x]−sumP[y])
(sumP[x]−sumP[y])
除到左边去(
在做斜率优化时一定要注意除数的正负性，否则推出的式子可能会错！)
(f[x]+sum[x])−(f[y]+sum[y])sumP[x]−sumP[y]<X[i]
在单调队列里，
(f[x]+sum[x])−(f[y]+sum[y])sumP[x]−sumP[y]
可以看作是队列中相邻的
x
点和y点连线的斜率，时刻维护单调队列中的元素的连线斜率(
(f[x]+sum[x])−(f[y]+sum[y])sumP[x]−sumP[y]
)单调递增(下凸壳)即可。
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 2100000
using namespace std;
typedef long long int LL;
int n;
LL f[MAXN];
LL P[MAXN],C[MAXN],X[MAXN];
LL sum[MAXN],sumP[MAXN];
int q[MAXN];
inline LL W(int j,int i)
{
return X[i]*(sumP[i]-sumP[j])-(sum[i]-sum[j]);
}
inline LL fracup(int x,int y)
{
return (f[x]+sum[x])-(f[y]+sum[y]);
}
inline LL fracdn(int x,int y) //x>y
{
return sumP[x]-sumP[y];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&X[i],&P[i],&C[i]);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+P[i]*X[i],sumP[i]=sumP[i-1]+P[i];
int h=1,t=0;
q[++t]=0;
for(int i=1;i<=n;i++)
{
while(h<t&&fracup(q[h+1],q[h])<X[i]*fracdn(q[h+1],q[h])) h++;
f[i]=f[q[h]]+W(q[h],i)+C[i];
while(h<t&&fracup(q[t],q[t-1])*fracdn(i,q[t])>=fracup(i,q[t])*fracdn(q[t],q[t-1])) t--;
q[++t]=i;
}
printf("%lld\n",f[n]);
return 0;
}
2.BZOJ 1010 玩具装箱toy
题目链接
http://www.lydsy.com/JudgeOnline/problem.php?id=1010
思路
令
f[i]=[1,i]
部分装箱，且玩具i是玩具
[1,i]
装箱后，最右边那个箱子的右端点，装箱的最少费用。
容易得到DP方程：
f[i]=min1≤j<i{f[j]+(i−j−1+sum[i]−sum[j]−L)2}
为了方便叙述，以下约定
L′=L−1,sum′[i]=sum[i]+i
DP方程就变成了：
f[i]=min1≤j<i{f[j]+(sum′[i]−sum′[j]−L′)2}
设
x>y
，且对于
f[i]
而言，
f[x]
比
f[y]
更优，则
f[x]+(sum′[i]−sum′[x]−L′)2<f[y]+(sum′[i]−sum′[y]−L′)2
(f[x]+sum[x]2−2sum[x](sum[i]−L))−(f[y]+sum[y]2−2sum[y](sum[i]−L))<0
f[x]+sum[x]2−f[y]−sum[y]2<(sum[x]−sum[y])2(sum[i]−L)
(sum[x]−sum[y])
除到左边去(因为保证是正数，所以不等号不变，这里
再次强调推公式过程中，要注意
不等式除法改变不等号方向的问题！)
f[x]+sum[x]2−f[y]−sum[y]2sum[x]−sum[y]<2(sum[i]−L)
代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define MAXN 110000
using namespace std;
typedef long long int LL;
int n;
LL L;
LL C[MAXN];
LL sum[MAXN]; //sum[i]=sigma C[j](1<=j<=i)+i
LL f[MAXN];
int q[MAXN],h=1,t=1;
LL fracup(int x,int y)
{
return (f[y]+sum[y]*sum[y])-(f[x]+sum[x]*sum[x]);
}
LL fracdn(int x,int y) //y>x
{
return sum[y]-sum[x];
}
int main()
{
scanf("%d%lld",&n,&L);
L++;
for(int i=1;i<=n;i++)
{
scanf("%lld",&C[i]);
sum[i]=sum[i-1]+C[i];
}
for(int i=1;i<=n;i++) sum[i]+=i;
q[h]=0;
for(int i=1;i<=n;i++)
{
while(h<t&&fracup(q[h],q[h+1])<2*(sum[i]-L)*fracdn(q[h],q[h+1])) h++;
f[i]=f[q[h]]+(sum[i]-sum[q[h]]-L)*(sum[i]-sum[q[h]]-L);
while(h<t&&fracup(q[t-1],q[t])*fracdn(q[t],i)>=fracup(q[t],i)*fracdn(q[t-1],q[t])) t--;
q[++t]=i;
}
printf("%lld\n",f[n]);
return 0;
}
