[HNOI2008] 玩具装箱
题目描述
P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P 教授有编号为 1 ~n 的 n 件玩具，第 i件玩具经过压缩后的一维长度为 C_i。
为了方便整理，P 教授要求：
-
在一个一维容器中的玩具编号是连续的。
-
同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 i 件玩具到第 j 个玩具放到一个容器中，那么容器的长度将为 x=j-i+ci+c[i+1]+…+c[j]。
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 x，其制作费用为 (x-L)^2。其中 L 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 L。但他希望所有容器的总费用最小。
输入格式
第一行有两个整数，用一个空格隔开，分别代表 n 和 L。
第 2 到 第 (n + 1) 行，每行一个整数，第 (i + 1) 行的整数代表第 i件玩具的长度 C_i。
输出格式
输出一行一个整数，代表所有容器的总费用最小是多少。
样例 #1
样例输入 #1
5 4
3
4
2
1
4
样例输出 #1
1
提示
对于全部的测试点，1<=n<=5*10^4,1<=L<=10^7,1<=Ci<=10^7
定义dp[i]=j表示假设只有前i个，得到的最小值为j
状态转移方程dp[i]=min(dp[j]+(j-i-1+pre[i]-pre[j])-L)^2) (0<=j<i) //dp[i]=k表示前i位的答案为j,pre为前缀和数组
#include<bits/stdc++.h>
using namespace std;
int n,l,a[50010],cnt;
long long pre[50010],dp[50010],k[50010];
struct Node
{
long long x,y;
};
Node x[50010];
int main()
{
cin>>n>>l;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
pre[i]=pre[i-1]+a[i];
dp[1]=(a[1]-l)*(a[1]-l);
x[++cnt]={2*(pre[1]+1),dp[1]+(pre[1]+1)*pre[1]+1};
for(int i=2;i<=n;i++)
{
int le=1,r=cnt-1,mid,u,v;
while(l<r)
{
mid=le+r>>1;
if(k[mid]<=pre[i]+i-1-l)
le=mid;
else
r=mid-1;
}
if(le==1)
{
if(k[le]<=pre[i]+i-1-l&&pre[i]+i-1-l<=k[le+1])
{
dp[i]=x[le+1].y-x[le+1].x*(pre[i]+i-1-l);
}
else
dp[i]=x[le].y-x[le].x*(pre[i]+i-1-l);
}
else
{
if(k[le-1]<=pre[i]+i-1-l&&pre[i]+i-1-l<=k[le])
{
dp[i]=x[le].y-x[le].x*(pre[i]+i-1-l);
}
else
dp[i]=x[le+1].y-x[le+1].x*(pre[i]+i-1-l);
}
dp[i]+=(pre[i]+i-1-l)*(pre[i]+i-1-l);
dp[i]=min(dp[1],(pre[i]+i-1-l)*(pre[i]+i-1-l));
u=2*(pre[i]+i),v=dp[i]+(pre[i]+i)*(pre[i]+i);
while((v-x[cnt].y)/(u-x[cnt].x)<k[cnt-1]&&cnt!=1)
cnt--;
k[cnt]=(v-x[cnt].y)/(u-x[cnt].x);
x[++cnt]={v,u};
}
cout<<dp[n];
}
样例竟然过了