首页 > 代码库 > ZOJ 3469 Food Delivery（区间DP）

ZOJ 3469 Food Delivery（区间DP）

2024-07-08 23:53:49   221人阅读

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4255

题意：n个人订餐。n个人位于一条线上，饭店也在这条线上。每个人有一个脾气值p。若第i分钟得到他预定的饭不满意度为p*i。送饭人的速度已知。求一种送饭顺序使得总不满意度最小。

思路：设f[i][j][0],f[i] [j][1]分别表示将[i,j]区间的送完，最后停在左边或右边的最小不满意度。那么我们在DPf[i][j][0]时可以从f[i+1][j]进行转 移。我们发现，我们需要记录f[i+1][j]取得最优值时需要的时间t[i+1][j]，这样我们才知道i得到饭时的时间，此时我们发现就不满足最优子 结构了，我们记f[i+1][j]和t[i+1][j]为二元组(X,Y)，若有两种情况(X,Y)=(10,5),(X,Y)=(5,10)，那么我们 保存前者还是后者呢？按照题意，我们应该保存后者，因为后者的不满意度最小，但是时间大，转移到的f[i][j][0]不见得比(10,5)这组优。。。 那么应该怎么做的？我们发现，前面的时间每增加1,其实后面还没有遍历的人的所有人的时间就会增加1,其相应不满意度的增加也就能算出来，我们若把这个不 满意度也加到当前DP的子问题中，那么t就不需要保存，比如从f[i+1][j][1]向f[i][j][0]转移时我们只需要直接计算j走到i的时间， 而f[i+1][j][0]所用的时间对后面产生的影响我们已经加入f[i+1][j][0]了，这样就满足最优子结构了。。。

 

i64 f[N][N][2],v,x,S[N];int n;struct node{    i64 x,y;};node a[N];int cmp(node a,node b){    return a.x<b.x;}i64 Cost(int i,int j){    if(i>j) return 0;    return S[j]-S[i-1];}void up(i64 &x,i64 y){    if(x>y) x=y;}int main(){    Rush(n)    {        RD(v,x);        int i,j;        FOR1(i,n) RD(a[i].x,a[i].y);        a[++n].x=x; a[n].y=0;        sort(a+1,a+n+1,cmp);        int pos;        FOR1(i,n) if(a[i].x==x) break;        pos=i;        FOR1(i,n) S[i]=S[i-1]+a[i].y;        FOR1(i,n) FOR1(j,n) f[i][j][0]=f[i][j][1]=inf;        f[pos][pos][0]=f[pos][pos][1]=0;        i64 temp;        for(i=pos;i>=1;i--) for(j=pos;j<=n;j++)        {            if(i==j) continue;            temp=Cost(1,i-1)+Cost(j+1,n);            up(f[i][j][0],f[i+1][j][0]+(temp+a[i].y)*(a[i+1].x-a[i].x));            up(f[i][j][0],f[i+1][j][1]+(temp+a[i].y)*(a[j].x-a[i].x));            up(f[i][j][1],f[i][j-1][0]+(temp+a[j].y)*(a[j].x-a[i].x));            up(f[i][j][1],f[i][j-1][1]+(temp+a[j].y)*(a[j].x-a[j-1].x));        }        i64 ans=min(f[1][n][0],f[1][n][1]);        ans*=v;        PR(ans);    }}

 

 

 

 


联系
我们