HDU 3507 Print Article（斜率优化DP）

题目链接

题意 ： 一篇文章有n个单词，如果每行打印k个单词，那这行的花费是，问你怎么安排能够得到最小花费，输出最小花费。

思路 ： 一开始想的简单了以为是背包，后来才知道是斜率优化DP，然后看了网上的资料，看得还挺懂的，不过我觉得如果以后真遇到斜率DP，要推起来肯定不简单。。。。。

网上资料1

网上资料2

#include <iostream>
#include <stdio.h>

using namespace std;

int q[500005],dp[500005],sum[500005] ;
int head,tail,m,n ;

// dp[i]= min{ dp[j]+M+(sum[i]-sum[j])^2 };
int getDP(int i,int j)
{
    return dp[j] + m + (sum[i]-sum[j]) * (sum[i]-sum[j]) ;
}
int getUP(int j,int k)//求yj-yk
{
    return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]) ;
}
int getDOWM(int j,int k)//求xj-xk
{
    return 2*sum[j]-2*sum[k] ;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i = 1 ; i <= n ; i++)
            scanf("%d",&sum[i]) ;
        sum[0] = dp[0] = 0 ;
        for(int i = 1 ; i <= n ; i++)
            sum[i] += sum[i-1] ;
        head = tail= 0 ;
        q[tail++] = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            //如果满足g[j,k]=yj-jk/xj-xk<sum[i]代表这j的决策比k的决策要更优,所以k可以直接淘汰了。
            while(head+1 < tail && getUP(q[head+1],q[head]) <= sum[i] * getDOWM(q[head+1],q[head]))
            head++ ;
            dp[i] = getDP(i,q[head]) ;
            //g[i,j]<g[j,k]，那么j点便永远不可能成为最优解，可以直接将它踢出我们的最优解集。
            while(head+1 < tail && getUP(i,q[tail-1]) * getDOWM(q[tail-1],q[tail-2]) <= getUP(q[tail-1],q[tail-2]) * getDOWM(i,q[tail-1]))
                tail-- ;
            q[tail++] = i ;
        }
        printf("%d
",dp[n]) ;
    }
    return 0;
}