zoj 3469 区间dp

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4255

这特喵的不就是河南省某届省赛那道开关灯的强化版题目吗。。。。

一是数据增强了可能爆int，所以用的LL才A，还有就是给出的坐标不一定有序注意排序，还有起点不一定是送餐点，要把起点也看做是一个点一共N+1个点。

dp[i][j][k]表示送完[i,j]之间的餐且此时处于左/右端点所消耗的价值，答案就是min(dp[1][N+1][0],dp[1][N+1][1])

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 const LL inf=2147483647;
 5 LL dp[1005][1005][2];
 6 LL pre[1005];
 7 struct node
 8 {
 9     int x,b;
10     bool operator<(const node& tmp)const{
11     return x<tmp.x;
12     }
13 }P[1005];
14 int main()
15 {
16     int N,V,X,i,j,k;
17    // freopen("in.txt","r",stdin);
18    ios::sync_with_stdio(false);
19     while(cin>>N>>V>>P[0].x){P[0].b=-9;
20         memset(pre,0,sizeof(pre));
21         for(i=0;i<=1001;++i)
22             for(j=0;j<=1001;++j) dp[i][j][0]=dp[i][j][1]=inf;
23         int x[1005],b[1005];
24         for(i=1;i<=N;++i)
25             cin>>P[i].x>>P[i].b;
26         sort(P,P+1+N);
27         for(i=0;i<=N;++i)
28         {
29             x[i+1]=P[i].x;
30             if(P[i].b==-9){dp[i+1][i+1][0]=dp[i+1][i+1][1]=0;P[i].b=0;}
31             pre[i+1]=pre[i]+P[i].b;
32         }
33         for(int len=1;len<=N+1;++len)
34         {
35             for(i=1,j=len;j<=N+1;++i,++j)
36             {
37                 if(dp[i][j][0]!=inf){
38                     if(i-1>0) dp[i-1][j][0]=min(dp[i-1][j][0],dp[i][j][0]+(x[i]-x[i-1])*V*(pre[i-1]+pre[N+1]-pre[j]));
39                     if(j+1<=N+1)dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][0]+(x[j+1]-x[i])*V*(pre[i-1]+pre[N+1]-pre[j]));
40                 }
41                 if(dp[i][j][1]!=inf){
42                     if(i-1>0) dp[i-1][j][0]=min(dp[i-1][j][0],dp[i][j][1]+(x[j]-x[i-1])*V*(pre[i-1]+pre[N+1]-pre[j]));
43                     if(j+1<=N+1){
44                             dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][1]+(x[j+1]-x[j])*V*(pre[i-1]+pre[N+1]-pre[j]));
45                     }
46                 }
47             }
48         }
49         cout<<min(dp[1][N+1][0],dp[1][N+1][1])<<endl;
50     }
51     return 0;
52 }