HDU3507 print article （斜率优化DP）

状态表示：dp[i]表示打印前i个单词的最小成本；s[i]维护前缀和。

状态转移：dp[i]=min(dp[j]+(s[i]-s[j])²)+m , 0<=j<i。

换成y=kx+b的形式：dp[j]+s[j]²=2*s[i]*s[j]+dp[i]-s[i]²-m。

算法步骤：1.枚举i=1...n，k=2*s[i]。

2.检查单调队列队头，排除决策.。

3.此时队头就是最优决策j，根据方程计算dp[i]。

4.加入新决策i，检查下凸性，删除队尾直至满足下凸性。

5.最优解为dp[n]。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=5e5+10;

 4 int dp[N],s[N],q[N];

 5 int n,m;

 6

 7 int GetY(int k1,int k2){//求y得差值

 8     return dp[k2]+s[k2]*s[k2]-(dp[k1]+s[k1]*s[k1]);

 9 }

10

11 int GetX(int k1,int k2){//求x的差值

12     return s[k2]-s[k1];

13 }

14

15 int GetVal(int i,int j){//得到dp[i]的值

16     return dp[j]+(s[i]-s[j])*(s[i]-s[j])+m;

17 }

18

19 int main(){

20     while(~scanf("%d%d",&n,&m)){

21         s[0]=0;

22         dp[0]=0;

23         for(int i=1;i<=n;i++){

24             scanf("%d",&s[i]);

25             s[i]+=s[i-1];

26         }

27         int head=0,tail=0;

28         q[tail++]=0;//单调队列 ，该队列要维护斜率单增

29         for(int i=1;i<=n;i++){

30             while(head+1<tail && GetY(q[head],q[head+1])<=2*s[i]*GetX(q[head],q[head+1]))

31                 head++;//排除之前的不是最优的决策

32             dp[i]=GetVal(i,q[head]);

33

34             while(head+1<tail && GetY(q[tail-1],i)*GetX(q[tail-2],q[tail-1])<=GetY(q[tail-2],q[tail-1])*GetX(q[tail-1],i))

35                 tail--;//维护下凸包，不满足则删去

36             q[tail++]=i;

37         }

38         printf("%d\n",dp[n]);

39     }

40     return 0;

41 }

HDU3507 print article （斜率优化DP）的相关教程结束。