状态方程为dp[i]=min{dp[j]+(sum[i]-sum[j])^2+m} ,0<=j<i
状态转移是O(n)的，总体复杂度为O(n^2)，对于n=500000显然会超时
上网查了下，发现要用到斜率优化，找了些资料来看，理解了一下什么是斜率优化
这个题我是用代数方法维护单调队列的，几何方法暂时还不会
首先,把方程变化一下
Dp[i]=min{dp[j]+sum[j]^2-2*sum[i]*sum[j]}+s[i]^2+m，把不影响决策j的放到括号外面
设w[j,i]= dp[j]+sum[j]^2-2*sum[i]*sum[j],需要证明的是，对于j1<j2<i，若w[j1,i]>w[j2,i],那么对于i’>i,w[j1,i’]>w[j2,i’],即j1对之后的决策是没用的
令h(x)=dp[x]+sum[x]^2
若w[j1,i]<w[j2,i],那么h(j1)-2*sum[i]*sum[j1]<h(j2)-2*sum[i]*sum[j2]
即(h(j1)-h(j2))/(sum[j1]-sum[j2])>2*sum[i]
这个表达式与w[j1,i]<w[j2,i]等价，
记s[j1,j2]= (h(j1)-h(j2))/(sum[j1]-sum[j2]),即2*sum[i]<s[j1,j2]的时候，j1比j2更优，2*sum[i]>=s[j1,j2]的时候，j2比j1更优，由于sum[i]是随i单调递增的，即i’>i时，sum[i’]>sum[i]，即此后j2总是比j1更优，可以舍弃j1
于是，我们需要维护一个单调递增的序列,j0<j1<j2<…且2*sum[i]<s[j0,j1]<s[j1,j2]<…即最优性质是递减的，队头总是最优的
当新加入一个点时，我们维护这个单调序列的单调性，如果要取对于点i的最优决策点，必须满足2*sum[i]<s[j0,j1]，否则，队头出队，直到只剩一个点。需要注意的是j0,j1,j2虽然是递增的，但是不一定是连续的！
#include<iostream> #include<memory.h> #include<string> #include<cstdio> #include<algorithm> #include<math.h> #include<stack> #include<queue> #include<vector> #include<map> using namespace std; const int MAX=500005; long long dp[MAX],sum[MAX]; int p[MAX],head,tail; long long get1(int i,int j) { return dp[i]-dp[j]+sum[i]*sum[i]-sum[j]*sum[j]; } long long get2(int i,int j) { return sum[i]-sum[j]; } int Pop(int i) { while(head<tail&&get1(p[head],p[head+1])>=2*sum[i]*get2(p[head],p[head+1])) head++; return p[head]; } void Push(int i) { while(head<tail&&get1(p[tail],i)*get2(p[tail-1],p[tail])<=get1(p[tail-1],p[tail])*get2(p[tail],i)) tail--; tail++; p[tail]=i; } int main() { int i,j,n,m; long long k; while(scanf("%d%d",&n,&m)!=EOF) { sum[0]=0; for(i=1;i<=n;i++) { scanf("%lld",&k); sum[i]=sum[i-1]+k; } dp[0]=0; head=0; tail=-1; Push(0); for(i=1;i<=n;i++) { j=Pop(i); //cout<<j<<endl; dp[i]=dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m; Push(i); } printf("%lld/n",dp[n]); } return 0; }
