hdu3507

发表于 | 分类于 | 阅读数 次

链接:hdu3507

题解

  • dp方程很容易得到dp[i]表示输出到i的最小花费,dp[i]=min(dp[j]+),后面那坨有i有j，显然不能直接单调队列优化

  • 考虑某个状态k(k显然是

    整理一下，把与i无关的放一边
    得到

  • 到这里斜率就出来了,剩下的就是一个简单的斜率优化dp

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e6+7;
    int n,m,q[N],tail,head;
    int dp[N],sum[N];
    inline int X(int a,int b){return (sum[a]-sum[b])*2;}
    inline int Y(int a,int b){return dp[a]-dp[b]+sum[a]*sum[a]-sum[b]*sum[b];}
    int main(){
    	while(~scanf("%d%d",&n,&m)){
    		head=tail=1;
    		q[1]=0;
    		rep(i,1,n){
    			scanf("%d",&sum[i]);
    			sum[i]+=sum[i-1];
    			while(head<tail&&Y(q[head+1],q[head])<=X(q[head+1],q[head])*sum[i])++head;
    			dp[i]=(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m+dp[q[head]];
    			while(head<tail&&Y(i,q[tail])*X(q[tail],q[tail-1])<=Y(q[tail],q[tail-1])*X(i,q[tail]))--tail;
    			q[++tail]=i;
    		}
    		printf("%d\n",dp[n]);
    	}
    	return 0;
    }