当前位置:编程学习 > C/C++ >>

Zoj 3469 Food Delivery (DP_好题)


题目大意:送餐员送餐问题。有n个人叫餐,每个人都在x轴上,并且每个人都有个坑爹度(和等餐时间有关,据说顾客认为坑爹值到一定程度他的小宇宙就要爆发).现在送餐员从x轴上的某点出发,路上奔跑速度是v,要一次性把所有餐送完。叫餐的人得到餐的时间和顺序不同,坑爹度总和也就不同。合格的送餐员要让客户体验最好,请问最少坑爹度和为多少

解题思路:下午开了2011年浙大2月份的月赛,做了三题,这题没出,易做图暴了。这题要考虑当前状态对后续状态的影响,相当经典,很锻炼思维,这种题目我喜欢。
    先说下本题的模型,送餐的顺序是一个从x位置开始的从1...n的一个全排列,我们要做的是找一个全排列它的总坑爹值最小。
    现在设想已经找到几个点相对位置是 3 2 1 x 4 5 6,使坑爹值小的策略是先送中间的再往两边送,因为送完中间的可以顺着去送两边。
    如果已经计算好了x 1 4的最小坑爹值,如果不考虑坑爹值最小这个条件我们先找2或者5是不是都可以?选了以后对之前的状态不会影响,因为后面的时间影响不到前面的。得出一个结论,本模型无后效性。
     确定了无后效性,那就要考虑那个约束条件和状态,我们的决策是在x两边来回选择坑爹值小的,那么设dp[i][j][k]表示从第i个人到第j个人都已经送完餐最后停在k== 0 - 》左边,k == 1 -》右边的最小坑爹值。
      状态明确了转移也就睡到渠成了。dp[i][j][0] 可能从dp[i+1][j][0],dp[i+1][j][1]  (i+1在i右边,两个都在i左边)转移而来,dp[i][j][1]可能从dp[i][j-1][0],dp[i][j-1][1]转移而来。具体状态转移方程参见代码,很容易看懂。
     然后特别要注意的是每转移一次,都会增加一定的时间,水涨船高,后面的人拿到餐的时间也晚了,也就是说必须把对后面的影响考虑在当前状态下,并且对后面的每个人影响都是一样的,那么当前转移用时t,后面还有x人,当前的状态就要多加x*t,

测试数据:
5 1 0
1 1
2 2
3 3
4 4
5 5

C艹代码:
[cpp] 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
#define MAX 1100 
#define INF 1100000000 
#define min(a,b) ((a)<(b)?(a):(b)) 
 
 
struct node { 
     
    int x,v; 
}arr[MAX]; 
int dp[MAX][MAX][2]; 
int n,v,x,sum[MAX],ans; 
 
 
int cmp(node a,node b) { 
 
    return a.x < b.x; 

int GetRest(int l,int r) { 
 
    if (r < l) return 0; 
    return sum[r] - sum[l-1]; 

int Solve_Dp() { 
 
    int i,j,k,res,delay; 
 
 
    for (i = 1; i <= n; ++i)        //找restaurant 
        if (arr[i].x == x) res = i; 
    for (i = 1; i <= n; ++i) 
        for (j = 1; j <= n; ++j) 
            dp[i][j][0] = dp[i][j][1] = INF; 
 
 
    dp[res][res][0] = 0; 
    dp[res][res][1] = 0; 
    for (i = res; i >= 1; --i)//left 
        for (j = res; j <= n; ++j) {//right 
 
            if (i == j) continue; 
            //后面的值提前拿出来计算 
            delay = GetRest(1,i - 1) + GetRest(j + 1,n); 
            //停在左边 
            dp[i][j][0] = min(dp[i][j][0],dp[i+1][j][1]+(delay+arr[i].v)*(arr[j].x-arr[i].x));  //从[i+1,j]右边来 
            dp[i][j][0] = min(dp[i][j][0],dp[i+1][j][0]+(delay+arr[i].v)*(arr[i+1].x-arr[i].x));//从[i+1,j]左边来 
            //停在右边 
            dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][0]+(delay+arr[j].v)*(arr[j].x-arr[i].x));  //从[i,j-1]左边来 
            dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][1]+(delay+arr[j].v)*(arr[j].x-arr[j-1].x));//从[i,j-1]右边来 
        } 
 
    //最后停左边可以,停右边也可以 
    return min(dp[1][n][0],dp[1][n][1]); 

 
 
int main() 

    int i,j,k; 
     
     
    while (scanf("%d%d%d",&n,&v,&x) != EOF) { 
       
        for (i = 1; i <= n; ++i) 
            scanf("%d%d",&arr[i].x,&arr[i].v); 
        arr[++n].x = x,arr[n].v = 0; 
 
 
        memset(sum,0,sizeof(sum)); 
        sort(arr+1,arr+1+n,cmp);       //排序然后按照x将各个坐标分左右两边 
        for (i = 1; i <= n; ++i) 
            sum[i] = sum[i - 1] + arr[i].v; 
 
 
        ans = Solve_Dp(); 
        printf("%d\n",ans * v);       //当算时间的时候是dist/(v^-1),但是放到最后可以直接乘个v 
    } 


作者:woshi250hua
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,