bzoj1010 [HNOI2008] 玩具装箱toy

题意:给定一个序列${C_i}$,将这个序列分段,其中每段装入一个容器,$[i,j]$这段的容器的长度为$\sum_{k=j}^{i} C_k +i-j-1$,问序列中所有数全部分段装容器以后的最小花费。

容易得到最朴素的式子$dp[i]=min_{j=0}^{i-1} (dp[j]+(i-j-1+\sum_{k=j+1}^{i} {C_k}-L)^2)$

记录前缀和为$sum[i]$可以得到$dp[i]=min_{j=0}^{i-1} (dp[j]+(i-j-1+sum[i]-sum[j]-L)^2)$

直接算复杂度为$O(n^2)$,考虑斜率优化

上式为$dp[i]=min_{j=0}^{i-1} (dp[j]+(i+sum[i]-j-sum[j]-L-1)^2)$

令$f(i)=sum[i]+i$,则$dp[i]=min_{j=0}^{i-1} (dp[j]+(f(i)-f(j)-L-1)^2)$

假定对于$dp[i]$,有决策点$j,k(j<k)$,如果$k$比$j$更优,

那么$dp[j]+(f(i)-f(j)-L-1)^2)>dp[k]+(f(i)-f(k)-L-1)^2$

拆平方,移项得$dp[j]+f^2(j)-(dp[k]+f^2(k))+2(f(j)-f(k))\cdot(L+1)>2f(i)\cdot (f(j)-f(k))$

$\frac{dp[j]+f^2(j)-(dp[k]+f^2(k))}{f(j)-f(k)}<2(f(i)-L-1)$

$\frac{dp[j]+f^2(j)-(dp[k]+f^2(k))+2(L+1)(f(j)-f(k))}{f(j)-f(k)}<2f(i)$

$\frac{dp[j]+(f(j)+L+1)^2-dp(k)-(f(k)+L+1)^2}{2(f(j)-f(k))}<f(i)$

令$g(j,k)=\frac{dp[j]+(f(j)+L+1)^2-dp(k)-(f(k)+L+1)^2}{2(f(j)-f(k))}$,则当$g(j,k)<f(i)$时,$k$比$j$更优。

同时考虑一个情形,当$g(l,j)>g(j,k)$的时候,$j$一定不是最优决策点,简证:

  • 当$g(l,j)>f(i)$($i$为当前要更新的下标),j不是最优;
  • 当$g(l,j)\leq f(i)$,由于$g(l,j)>g(j,k)$,故$g(j,k)<f(i)$,$j$没有$k$优,$j$也不是最优决策点

得证,这个性质用于弹出队尾。

维护一个队列,当中存所有最优的决策点(对于当前$i$而言),$l$为队首,$r$为队尾,

当$g(q[l],q[l+1])<f(i)$时,弹掉队首;

当$g(q[r-1],q[r])<g(q[r],i)$时,弹掉队尾。

这样可以每次$O(1)$更新答案,总复杂度为$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50000+5;
ll dp[maxn],c[maxn],L,sum[maxn];
int n;
ll f(int i){return sum[i]+i;}
double g(int j,int k)
{
return (dp[j]-dp[k]+(f(j)+L)*(f(j)+L)-(f(k)+L)*(f(k)+L))/(2.0*(f(j)-f(k)));
}
int q[maxn];
int main()
{
scanf("%d%lld",&n,&L);L++;
for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+c[i];
int l=1,r=1;q[1]=0;
for(int i=1;i<=n;i++) {
while(l+1<=r && g(q[l],q[l+1])<f(i)) l++;
dp[i]=dp[q[l]]+(f(i)-f(q[l])-L)*(f(i)-f(q[l])-L);
while(r-1>=l && g(q[r-1],q[r])>g(q[r],i)) r--;
q[++r]=i;
}
printf("%lld\n",dp[n]);
return 0;
}