zoj3469

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

链接:zoj3469

题解

  • dp[i][j]表示区间i~j已经分配完之后的最小花费状态转移如下
  • dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(sum[i]+sum[n]-sum[j])*(nm[i+1].x-nm[i].x));
  • dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(sum[i]+sum[n]-sum[j])*(nm[j].x-nm[i].x));
  • dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1])*(nm[j].x-nm[i].x));
  • dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*(nm[j].x-nm[j-1].x));
    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
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #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;
    const ll inf=0x3f3f3f3f;
    struct node{
    	int x,c;
    	inline void init(int a,int b){x=a;c=b;}
    }nm[N];
    ll dp[N][N][2],sum[N];
    inline int cmp(node a,node b){return a.x<b.x;}
    int n,X,v;
    int main(){
    	while(~scanf("%d%d%d",&n,&v,&X)){
    		memset(dp,inf,sizeof(dp));
    		rep(i,1,n)scanf("%d%d",&nm[i].x,&nm[i].c);
    		nm[n+1].init(X,0);n++;
    		sort(nm+1,nm+n+1,cmp);
    		rep(i,1,n){sum[i]=sum[i-1]+nm[i].c;if(nm[i].x==X&&nm[i].c==0)dp[i][i][0]=dp[i][i][1]=0;}
    		rep(l,2,n)rep(i,1,n-l+1){
    			int j=i+l-1;
    			dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(sum[i]+sum[n]-sum[j])*(nm[i+1].x-nm[i].x));
    			dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(sum[i]+sum[n]-sum[j])*(nm[j].x-nm[i].x));
    			dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1])*(nm[j].x-nm[i].x));
    			dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*(nm[j].x-nm[j-1].x));
    		}
    		//rep(i,1,n)rep(j,1,n)cout<<dp[i][j][0]<<' '<<dp[i][j][1]<<endl;
    		printf("%lld\n",min(dp[1][n][0],dp[1][n][1])*v);
    	}
    	return 0;
    }