bzoj1010 [HNOI2008] 玩具装箱toy

Posted on |

题意：给定一个序列${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;
}