ZOJ 3469 Food Delivery （区间DP，经典）

题意：

　　在x轴上有一家外卖餐馆，有n个顾客站在x轴上不同坐标上且叫了外卖，每个人的脾气不同，每1分钟没有收到外卖就会增加F_i点愤怒值，而外卖小哥的车是有速度的v^-1/分钟，问怎样的送餐次序会让所有顾客的愤怒值之和最小？输出愤怒值之和！

思路：

　　此题是很经典了，比较现实的模型。

　　随便画画就知道小哥可以一下子往左一下子往右走，往返多次也是有可能的，取决于顾客的愤怒系数F_i。那么在考虑一个区间[L,R]时，其任一子区间都必须是已经被考虑过了。现在考虑区间[L,R]可以转移到哪里，明显可以分别转移到[L-1,R]和[L,R+1]，也就是往区间外送去1个人的外卖。由于送完区间[L,R]所有外卖后可能停在左/右边，得到的DP值不同，所以可以增加1维来区分送完后停的位置，设为dp[L][R][0/1]来记录愤怒之和。

　　这样还没有完，如果仅考虑当前区间[L,R]的顾客的愤怒值之和的话，无论怎样记录还是难以实现转移（这也是比较巧的地方）。但是如果你将其他未送达的顾客的愤怒值也先算进dp值的话就好转移了，比如区间[L,R]转移到[L,R+1]，那么[1,L-1]和[R+2,n]这些顾客就还在等外卖，每过1分钟他们的愤怒值也在增加，可以加到[L,R+1]的dp值进行考虑。

　　有没有可能dp[L][R][0]会转移到dp[L][R+1][0]？也就是从L走到R+1后还回到L处。经过推算，并不需要这样，不是很难想的。

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 struct node

 {

     int x, f;

 }p[N];

 int dp[N][N][], sum[N];

 int n, V, x, pos;

 inline int cmp(node a,node b){return a.x<b.x;}

 void init(int pos)

 {

     sum[]=;

     for(int i=; i<=n; i++)    sum[i]=sum[i-]+p[i].f;

     for(int i=; i<=n; i++)     //初始化

         for(int j=i; j<=n; j++)

             dp[i][j][]=dp[i][j][]=INF;

     dp[pos][pos][]=dp[pos][pos][]=;

 }

 int cal(int pos)

 {

     for(int j=pos; j<=n; j++)

     {

         for(int i=pos; i>; i--)

         {

             int f=sum[i-]+sum[n]-sum[j];   //f值之和*

             int L=dp[i][j][], R=dp[i][j][];

             dp[i-][j][]=min(dp[i-][j][], L+f*(p[i].x-p[i-].x));    //往左

             dp[i-][j][]=min(dp[i-][j][], R+f*(p[j].x-p[i-].x));

             dp[i][j+][]=min(dp[i][j+][], L+f*(p[j+].x-p[i].x));    //往右

             dp[i][j+][]=min(dp[i][j+][], R+f*(p[j+].x-p[j].x));

         }

     }

     return min(dp[][n][], dp[][n][])*V;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     while(~scanf("%d%d%d",&n,&V,&x))

     {

         for(int i=; i<=n; i++)

             scanf("%d%d", &p[i].x, &p[i].f);

         p[++n].x=x, p[n].f=;   //添加餐馆

         sort(p+, p+n+, cmp);

         for(int i=; i<=n; i++)

         {

             if(p[i].x==x)   //找到餐馆

             {

                 init(i);

                 cout<<cal(i)<<endl;

                 break;

             }

         }

     }

     return ;

 }

AC代码

巴特西

ZOJ 3469 Food Delivery （区间DP，经典）

最新文章

热门文章