hdu-3507-Print Article-斜率优化

我的理解：

备注：(i)代表只含i未知数的式子

形如以下表达式的状态转移：

dp[i]=dp[j]+(j,i);

dp[i]=dp[k]+(k,i);

假设对于i状态时，选择j状态比选择k状态更优.

那么dp[j]+(j,i)

如果上式可以转化成:dp[j]+(j)-(dp[k]+(k))/(j)-(k)<(i)

那么就可以用斜率优化进行优化：

设g[j,k]<(i)代表在i状态时，选择j状态比选择k状态更优。

对于g[i][j]

如果g[i][j]<(i),那么i状态比j状态更优，则抛弃j状态。

如果g[i][j]>=(i),那么g[j][k]>=(i),那么k状态比j状态要优，那么抛弃j状态。

即：

如果存在g[i][j]

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define maxn 550000 struct list { int x; int val; } node[maxn],p; int a[maxn]; int sum[maxn]; int dp[maxn]; int gety(int x,int y) { return dp[x]+sum[x]*sum[x]-dp[y]-sum[y]*sum[y]; } int tan(int x,int y,int z) { int ay=gety(z,y); int by=gety(y,x); int ax=2*(sum[z]-sum[y]); int bx=2*(sum[y]-sum[x]); if(ay*bx<=by*ax)return 1; return 0; } int pan(int a,int b,int c) { int ay=gety(b,a); int ax=2*(sum[b]-sum[a]); if(ay<=sum[c]*ax)return 1; return 0; } int main() { int n,m,i; while(~scanf(%d%d,&n,&m)) { sum[0]=0; for(i=1; i<=n; i++) { scanf(%d,&a[i]); sum[i]=sum[i-1]+a[i]; } int head,tail; head=1; tail=0; p.x=0; node[++tail]=p; memset(dp,0,sizeof(dp)); for(i=1; i<=n; i++) { p.x=i; while(tail>head&&pan(node[head].x,node[head+1].x,i))head++; int x=node[head].x; dp[i]=dp[x]+m+(sum[i]-sum[x])*(sum[i]-sum[x]); while(tail>head&&tan(node[tail-1].x,node[tail].x,i))tail--; node[++tail]=p; } cout<