题目大意：给出一串正数，将这一串数分成若干段，每一段的代价为这一段数的加和的平方+一个常数m,求最小代价。
不难写出DP转移方程： f[i]=max(f[j]+(sum[i]−sum[j])2+m) 但是，这样复杂度是 N2 的，对于 N≤500,000 显然是不行的，对于这种转移方程与i,j都有关的，可以用斜率优化来优化。
考虑k < <script type="math/tex" id="MathJax-Element-4887"><</script>j < <script type="math/tex" id="MathJax-Element-4888"><</script>i，若j比k更优，则
f[j]+(sum[i]−sum[j])2+m<f[k]+(sum[i]−sum[k])2+m 移项得,f[j]+sum[j]2−(f[k])+sum[k]22∗sum[j]−2∗sum[k]<sum[i] 如果将 f[j]+sum[j]2 看成纵坐标， 2∗sum[j] 看成横坐标，那么原来的不等式就可以表示为 y[j]−y[k]x[j]−x[k]<sum[i] 没错，这样不等式左边就是斜率的形式，如果斜率小于sum[i]，那么就说明j状态比k状态更优。由于sum[i]是递增的，每次新加入的点一定在最右边，所以可以很方便的利用队列优化到 O(N) 的复杂度。还是考虑k < <script type="math/tex" id="MathJax-Element-4895"><</script>j < <script type="math/tex" id="MathJax-Element-4896"><</script>i，若 k(k,j)>k(j,i) 那么j这个状态就无用了，理由如下： 对于之后的任意一个状态u，若 k(j,i)<sum[u] ，那么状态i显然比状态j优 若 k(j,i)≤sum[u] ，那么虽然j比i更优，但是 k(k,j)>k(j,i)≤sum[u] ，k比j更优 这样，队列中的点一定是下凸的（斜率随x的增大而增大），每次新加入一个点，就把所有k(x-1,x)>k(x,u)的节点x删除。由于曲线是下凸的，所以把前面的所有k小于sum[u]的节点删除以后，剩下的队列头就是最优状态。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 500006 #define LL long long using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline LL _read(){ LL sum=0;char ch=nc(); while(!(ch>='0'&&ch<='9')){ch=nc();if(ch==EOF)return -1e9;} while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc(); return sum; } LL n,m,hed,tal,que[maxn],px[maxn],py[maxn],f[maxn],a[maxn],sum[maxn]; double k(int x,int y){ if(px[x]==px[y])return py[x]>py[y]?-1e9:1e9; return (py[y]-py[x])/(px[y]-px[x]); } void pop(double x){while(hed<tal&&k(que[hed],que[hed+1])<x)hed++;} void push(int x){ while(tal>hed&&k(que[tal-1],que[tal])>k(que[tal],x))tal--; que[++tal]=x; } int main(){ freopen("print.in","r",stdin); freopen("print.out","w",stdout); while((n=_read())!=-1e9){ m=_read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(a[i]=_read()); f[1]=a[1]*a[1]+m;hed=0;que[tal=1]=1;px[1]=2*sum[1];py[1]=f[1]+sum[1]*sum[1]; for(int i=2;i<=n;i++){ pop(sum[i]);f[i]=f[que[hed]]+(sum[i]-sum[que[hed]])*(sum[i]-sum[que[hed]])+m; px[i]=2*sum[i];py[i]=f[i]+sum[i]*sum[i]; push(i); } printf("%lld\n",f[n]); } return 0; }