hdu2829

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

链接:hdu2829

题解

  • 先介绍斜率优化做法
  • 我们用res[i]表示1~i的区间权值,sum[i]表示1~i的前缀和,那么区间a+1~b的权值为res[b]-res[a]-sum[a]*(sum[b]-sum[a])
  • dp[j][i]表示前i个数断了j次的最小权值
  • 则dp[j][i]=min(dp[j-1][k]+res[i]-res[k]-sum[k]*(sum[i]-sum[k]))
  • 剩下的和hdu3507一样的
    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
    33
    34
    35
    36
    37
    38
    39
    40
    41

    #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=1e3+7;
    int n,m,q[N];
    ll dp[N][N],sum[N],res[N];
    inline ll Y(int a,int b,int c){return dp[c][a]-res[a]+sum[a]*sum[a]-dp[c][b]+res[b]-sum[b]*sum[b];}
    inline ll X(int a,int b){return sum[a]-sum[b];}
    inline void init(){
    	rep(i,1,n){
    		scanf("%d",&sum[i]);
    		res[i]=res[i-1]+sum[i]*sum[i-1];
    		sum[i]+=sum[i-1];
    	}
    }
    int main(){
    	while(~scanf("%d%d",&n,&m)&&(n||m)){
    		init();
    		rep(i,1,n)dp[0][i]=res[i];
    		rep(j,1,m){
    			int head=1,tail=1;q[1]=0;
    			rep(i,1,n){
    				while(head<tail&&Y(q[head+1],q[head],j-1)<sum[i]*X(q[head+1],q[head]))++head;
    				dp[j][i]=dp[j-1][q[head]]+res[i]-res[q[head]]-sum[q[head]]*(sum[i]-sum[q[head]]);
    				while(head<tail&&Y(i,q[tail],j-1)*X(q[tail],q[tail-1])<=Y(q[tail],q[tail-1],j-1)*X(i,q[tail]))tail--;
    				q[++tail]=i;
    			}
    		}
    		
    		printf("%lld\n",dp[m][n]);
    	}
    	return 0;
    }