记录编号	58041	评测结果	AAAAAAAAAA
题目名称	开灯	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.123 s
提交时间	2013-04-16 15:23:33	内存使用	26.07 MiB

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int d[2000];
    int w[2000];
    int sum[2000][2000];
    int W;
    int N,V,Time,minn,cost;
    int dp[1001][1001][2];
    void init(){
    freopen("night.in","r",stdin);
    freopen("night.out","w",stdout);
    scanf("%d%d",&N,&V);
    for (int i=1;i<=N;i++){
    scanf("%d%d",&d[i],&w[i]);
    W+=w[i];
    }
    for (int i=1;i<=N;i++)
    {
    sum[i][i]=w[i];
    for (int j=i+1;j<=N;j++)
    sum[i][j]=sum[i][j-1]+w[j];
    }
    }
    long long min(long long a,long long b){
    return a<b?a:b;
    }
    long long DP(int left,int right,int c){
    if (left>V) return -1;
    if (right<V)return -1;
    if (left==0 || right==N+1 || left>right) return -1;
    if (dp[left][right][c]!=-1) return dp[left][right][c];
    long long tmp1,tmp2,tmp3,tmp4;
    long long cost1,cost2,cost3,cost4;
    int ans=2000000000;
    if (c==0){
    cost1=(d[left+1]-d[left])*(W-sum[left+1][right]);
    cost2=(d[right]-d[left])*(W-sum[left+1][right]);
    tmp1=DP(left+1,right,0);
    tmp2=DP(left+1,right,1);
    if (tmp1!=-1){
    ans=min(ans,tmp1+cost1);
    }
    if (tmp2!=-1){
    ans=min(ans,tmp2+cost2);
    }
    }
    if (c==1){
    cost3=(d[right]-d[left])*(W-sum[left][right-1]);
    cost4=(d[right]-d[right-1])*(W-sum[left][right-1]);
    tmp3=DP(left,right-1,0);
    tmp4=DP(left,right-1,1);
    if (tmp3!=-1){
    ans=min(ans,tmp3+cost3);
    }
    if (tmp4!=-1){
    ans=min(ans,tmp4+cost4);
    }
    }
    if (ans==2000000000) ans=-1;
    dp[left][right][c]=ans;
    return dp[left][right][c];
    }
    void work(){
    memset(dp,-1,sizeof(dp));
    dp[V][V][1]=0;
    dp[V][V][0]=0;
    dp[1][N][0]=DP(1,N,0);
    dp[1][N][1]=DP(1,N,1);
	long long ans=min(dp[1][N][0],dp[1][N][1]);
	if (dp[1][N][0]==-1) ans=dp[1][N][1];
	if (dp[1][N][1]==-1) ans=dp[1][N][0];
    printf("%d",ans);
    }
    int main()
    {
    init();
    work();
    return 0;
    }