Problem Description Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
hdu 3507 Print Article(斜率优化dp) 随笔
M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.  

 

Input There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤  500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.  

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 Output A single number, meaning the mininum cost to print the article.  

 

Sample Input 5 5 5 9 5 7 5   Sample Output 230   思路:dp[i]=dp[j]+(sum[i]-sum[j])^2 是该题的状态转移方程 但是我们只是关注斜率的优化 用一个单调队列来维护 由于这题的sum并是非严格的单调递增 所以我们不能用double来求斜率而是分别求dy和dx http://www.cnblogs.com/MashiroSky/p/6009685.html 这是斜率优化的博客 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long int
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int dp[500007];
int n,m;
int a[500007];
int sum[500007];
int q[500007];
int getup(int j,int k){
    return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];
}
int getdown(int j,int k){
    return sum[j]-sum[k];
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            cin>>a[i],sum[i]=sum[i-1]+a[i];
        int head,tail;
        head=tail=0;
        q[tail++]=0;
        for(int i=1;i<=n;i++){
            while(head+1<tail && getup(q[head+1],q[head])<=2*sum[i]*getdown(q[head+1],q[head]))
                ++head;
            dp[i]=dp[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m;
            while(head+1<tail && getup(i,q[tail-1])*getdown(q[tail-1],q[tail-2])<=getup(q[tail-1],q[tail-2])*getdown(i,q[tail-1]))
                --tail;
            q[tail++]=i;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄