ZOJ 3469 Food Delivery(区间DP好题)-白红宇

ZOJ 3469 Food Delivery(区间DP好题)

阅读量：5316 次

发布时间：2019-06-14

本文共 2115 字，大约阅读时间需要 7 分钟。

题目链接：

题目大意：

在x轴上有n个客人，每个客人每分钟增加的愤怒值不同。给出客人和餐厅的位置，以及客人每分钟增加的愤怒值，

和送餐行走一公里需要的时间，问送完n个客人的外卖最小愤怒值。

解题思路：

如果要访问完[i,j]，那么它的子区间一定访问完了。

用dp[i][j][0]表示访问完区间[i,j]并留在左端点，dp[i][j][1]表示访问完区间[i,j]并留在右端点。

把饭店那个地方也加进去作为点。从饭店那个点往两边进行DP；

dp[i][j][0] 可以根据dp[i+1][j][0]和dp[i+1][j][1]得到。

dp[i][j][1] 可以根据dp[i][j-1][0]和dp[i][j-1][1]得到。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              11 #include
               
                12 #include
                
                 13 #define lc(a) (a<<1)14 #define rc(a) (a<<1|1)15 #define MID(a,b) ((a+b)>>1)16 #define fin(name) freopen(name,"r",stdin)17 #define fout(name) freopen(name,"w",stdout)18 #define clr(arr,val) memset(arr,val,sizeof(arr))19 #define _for(i,start,end) for(int i=start;i<=end;i++)20 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);21 using namespace std;22 typedef long long LL;23 const int N=1e3+5;24 const int INF=0x3f3f3f3f;25 const double eps=1e-10;26 27 struct node{28 int x,b;29 }p[N];30 int sum[N];31 int dp[N][N][2]; //用dp[i][j][0]表示访问完区间[i,j]并留在左端点，dp[i][j][1]表示访问完区间[i,j]并留在右端点。32 33 bool cmp(node a,node b){34 return a.x
                 
                  >n>>v>>st){41 for(int i=1;i<=n;i++){42 cin>>p[i].x>>p[i].b;43 }44 p[++n].x=st;45 p[n].b=0;46 sort(p+1,p+1+n,cmp);47 int pos;48 for(int i=1;i<=n;i++){49 sum[i]=sum[i-1]+p[i].b;50 if(p[i].x==st)51 pos=i;52 }53 memset(dp,0x3f,sizeof(dp));54 dp[pos][pos][0]=dp[pos][pos][1]=0;55 for(int i=pos;i>=1;i--){56 for(int j=pos;j<=n;j++){57 if(i==j) continue;58 //如果从i+1这个点移动到i花费了时间t，那么除了i等待了t.59 //其它所有还没收到午餐的用户也都等待了t，因此要把他们的不满意度都算上60 dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(sum[i]+sum[n]-sum[j])*(p[i+1].x-p[i].x));61 dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(sum[i]+sum[n]-sum[j])*(p[j].x-p[i].x));62 63 dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1])*(p[j].x-p[i].x));64 dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*(p[j].x-p[j-1].x));65 }66 }67 printf("%d\n",v*min(dp[1][n][0],dp[1][n][1]));68 }69 return 0;70 }