題目鏈接：hdu 3507 Print Article
題意：
每個字有一個值，現在讓你分成k段打印，每段打印需要消耗的值用那個公式計算，現在讓你求最小值
題解：
設dp[i]表示前i個字符需要消耗的最小值，那么有dp[i]=min{dp[k]+(sum[i]-sum[k])2+m)}(k<i)。
這樣是n2?的做法。
考慮用斜率優化：
設k<j,對于dp[i]，從k+1到i為一段比j+1到i為一段更優。
那么有
dp[j]+(sum[i]-sum[j])2+m<=dp[k]+(sum[i]-sum[k])2+m
整理得：
dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k])/sum[j]-sum[k]<=2*sum[i]。
不等式的右邊就是一個斜率，然后用單調隊列優化，做到O(n)的復雜度。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=5e6+7; 6 int n,m,dp[N],sum[N],Q[N],head,tail; 7 8 int getx(int j,int k){return sum[j]-sum[k];} 9 int gety(int j,int k){return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];} 10 int check(int i,int j,int k){return gety(i,j)*getx(j,k)<=gety(j,k)*getx(i,j);} 11 12 int main() 13 { 14 while(~scanf("%d%d",&n,&m)) 15 { 16 F(i,1,n)scanf("%d",sum+i),sum[i]+=sum[i-1]; 17 head=1,tail=0; 18 Q[++tail]=0; 19 F(i,1,n) 20 { 21 while(head<tail&&gety(Q[head+1],Q[head])<=2*sum[i]*getx(Q[head+1],Q[head]))head++; 22 dp[i]=dp[Q[head]]+(sum[i]-sum[Q[head]])*(sum[i]-sum[Q[head]])+m; 23 while(head<tail&&check(i,Q[tail],Q[tail-1]))tail--; 24 Q[++tail]=i; 25 } 26 printf("%d\n",dp[n]); 27 } 28 return 0; 29 }
?
)
