Time Limit:10000MS Memory Limit:65536K Description P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 Input 第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7 Output 输出最小费用 Sample Input
5 4
3
4
2
1
4
Sample Output
1
Source xinyue |
题目：http://mail.bashu.cn:8080/bs_oj/showproblem?problem_id=2430
题意：题目短，还是中文的。。。= =
分析：很容易想到一个状态转移方程f[ i ]=min{ f[ j-1 ] + ( i- j +w[ j , i ] - L)^2 } ，当然这个是要超时的O(n^2)
惯例，我们写详细的方程
f[ i ]=min{ f[ j-1 ] + ( i- j +w[ j , i ] - L)^2 } (1<=j<=i)
w[ l , r ]=c[ l ] + c [ l+1 ] + ...+ c[ r ]
设： s[ i ]= sum{ c[ 1 ] + c [ 2 ]+ ... + c[ i ]}
那么有
( i- j +w[ j , i ] - L)^2
= ( i- j + s[ i ] - s[ j-1 ] - L)^2
=[ ( i + s[i ] - L ) - ( j + s[ j- 1] ) ]^2 注：将与 j 无关的变量拿到一边，方面下面斜率优化
=( i + s[i ] - L )^2 - 2*( i + s[i ] - L ) * ( j + s[ j- 1] ) + ( j + s[ j- 1] )^2
还是照样可以YY出以下公式：
f[ i ]=min{ f[ j-1 ] + ( j + s[ j- 1] )^2 - 2*( i + s[i ] - L ) * ( j + s[ j- 1] ) } + ( i + s[i ] - L )^2 无关变量放外面
设： a=2*( i + s[i ] - L ) x=( j + s[ j- 1] ) y=f[ j-1 ] + ( j + s[ j- 1] )^2
则原式编程求函数 G=-ax +y的最小值，转换下成 y = ax + G
然后就是明显的斜率优化了。。。
PS：这题调试了好久，主要是边界的一些问题，不过一道题调试久了，正确率就高了，然后就1Y了
代码：
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=55555;
typedef long long LL;
LL f[mm],s[mm];
int q[mm];
int i,j,n,l,r,L;
bool TRight(LL ax,LL ay,LL bx,LL by,LL cx,LL cy)
{
return (ax-bx)*(cy-by)>=(ay-by)*(cx-bx);
}
LL gx(int i)
{
return i+s[i-1];
}
LL gy(int i)
{
return (i+s[i-1])*(i+s[i-1])+f[i-1];
}
LL get(int i,LL a)
{
return gy(i)-a*gx(i);
}
int main()
{
while(~scanf("%d%d",&n,&L))
{
for(i=1;i<=n;++i)
{
scanf("%d",&j);
s[i]=s[i-1]+j;
}
for(i=1;i<=n;++i)f[i]=2e9;
f[0]=l=0,r=-1;
for(i=1;i<=n;++i)
{
while(l<r&&get(q[l],2*(i+s[i]-L))>=get(q[l+1],2*(i+s[i]-L)))++l;
f[i]=f[i-1]+(s[i]-s[i-1]-L)*(s[i]-s[i-1]-L);
if(l<=r)f[i]=min(f[i],get(q[l],2*(i+s[i]-L))+(i+s[i]-L)*(i+s[i]-L));
while(l<r&&TRight(gx(q[r-1]),gy(q[r-1]),gx(q[r]),gy(q[r]),gx(i),gy(i)))--r;
q[++r]=i;
}
printf("%I64d\n",f[n]);
}
return 0;
}