[文章目录]
Description
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个 常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小.n<=50000
独自A了一道斜率优化DP的问题，好爽啊！！！
首先考虑DP方程：dp[i]表示前i个物品都装进去了的最小花费。
dp[i]=dp[j]+(i-j+sum[i]-sum[j]-1-L)2第一个优化，前缀和等于自己加上下标。
化简得：dp[i]=-2*(sum[j]+1+L)*sum[i]+dp[j]+(sum[j]+1+L)2+sum[i]2
然后，我们发现这个方程的k=-2*(sum[j]+1+L),b=dp[j]+(sum[j]+1+L)2,常数=sum[i]2
k单调递减，x单调递增。所以可以斜率优化。
下面的话可以跳过：
斜率优化，就是对于一个DP方程，类似kx+b，我们发现前面的每一个状态都是一个方程，只是x变化。
k还是单调的？？？所以考虑，对于每一个方程，我们画出一条直线，由于x是递增的，所以我们斜率大的直线一旦有一个x带入时的值比斜率稍小的直线不优，这条直线肯定就在以后的时光中都没有用了。等到将所有这样的直线都排除了之后，我们将x带入斜率最小的直线，获得的就是最优解。（不过为什么是正确的？？？）
因为，当我们DP完成时，我们加进去一个新的直线，由于k是单调的，这条直线的斜率一定是最小的。然后我们从队尾开始抵消。每次拿出两条直线k1,k2，找交点。判断两直线交点x值，将最尾端的直线排除。解释一下就是前一个斜率小的直线挡住斜率中的前半部分，斜率大的直线挡住后半部分，所以这条直线就没有用了。
经验：
1.对于斜率优化DP，方程一定是kx+b并且x，k是单调的。
2.类似赛车的那道题，队列里维护的一定是可见直线，就是将直线都画到一个图里，全部从最优的角度看可见。
3.可以通过样例尝试代码的判断。注意分母的正负
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
LL n,L,val,sum[50100],dp[50100];
int h,t,q[50100];
LL k(int id) {return -2ll*(sum[id]+1+L);}
LL b(int id) {return dp[id]+(sum[id]+L+1)*(sum[id]+L+1);}
bool check(int x,int y,LL data) {return (k(x)-k(y))*data>=b(y)-b(x);}
bool check_double(int x,int y,int z) {return (k(z)-k(y))*(b(x)-b(z))>=(k(z)-k(x))*(b(y)-b(z));}
int main()
{
scanf("%lld%lld",&n,&L);
for(int i=1;i<=n;i++)
{
scanf("%lld",&val);
sum[i]=sum[i-1]+val+1;
}
for(int i=1;i<=n;i++)
{
while(h<t&&check(q[h],q[h+1],sum[i])) h++;
dp[i]=k(q[h])*sum[i]+sum[i]*sum[i]+b(q[h]);
while(h<t&&check_double(i,q[t-1],q[t])) t--;
q[++t]=i;
}
printf("%lld",dp[n]);
return 0;
}开心