本文主要是介绍Food Delivery ZOJ - 3469，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469
按区间DP做 dp[i][j][0]代表i到j都处理完后停在左端i处 dp[i][j][1]代表停在右端j处
转移方程如下
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(ary[i+1].pos-ary[i].pos)*(sum[i]+sum[n]-sum[j]));
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(ary[j].pos-ary[i].pos)*(sum[i]+sum[n]-sum[j]));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(ary[j].pos-ary[i].pos)*(sum[i-1]+sum[n]-sum[j-1]));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(ary[j].pos-ary[j-1].pos)*(sum[i-1]+sum[n]-sum[j-1]));
这道题走法比较特殊 从起点x出发 不断拐弯 中间经过的点都不会跳过 所以dp[i][j][]可以直接从dp[i+1][j][] dp[i][j-1][]转移而来
第一个方程就代表 从j走到i+1然后直走到了i 和 从i+1走到j然后拐弯回到i
剩下三个类似
还有要注意的是 因为dp[i][j][0]代表i到j都处理完后停在左端i处 就是说i是最后走的 之前没走过 所以不可能从dp[i][j-1][]转移过来
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;struct node
{ll pos,val;
};node ary[maxn];
ll dp[maxn][maxn][2];
ll sum[maxn];
ll v,x;
int n;bool cmp(node n1,node n2)
{return n1.pos<n2.pos;
}int main()
{ll val1,val2;int l,i,j,p;while(scanf("%d%lld%lld",&n,&v,&x)!=EOF){for(i=1;i<=n;i++){scanf("%lld%lld",&ary[i].pos,&ary[i].val);}n++;ary[n].pos=x,ary[n].val=0;sort(ary+1,ary+n+1,cmp);j=0;for(i=1;i<=n;i++){if(j==0||ary[j].pos!=ary[i].pos) ary[++j]=ary[i];else ary[j].val+=ary[i].val;}n=j;for(i=1;i<=n;i++){sum[i]=sum[i-1]+ary[i].val;}memset(dp,0x3f,sizeof(dp));for(i=1;i<=n;i++){if(ary[i].pos==x){dp[i][i][0]=dp[i][i][1]=0;break;}}for(l=2;l<=n;l++){for(i=1;i+l-1<=n;i++){j=i+l-1;dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(ary[i+1].pos-ary[i].pos)*(sum[i]+sum[n]-sum[j]));dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(ary[j].pos-ary[i].pos)*(sum[i]+sum[n]-sum[j]));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(ary[j].pos-ary[i].pos)*(sum[i-1]+sum[n]-sum[j-1]));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(ary[j].pos-ary[j-1].pos)*(sum[i-1]+sum[n]-sum[j-1]));}}printf("%lld\n",v*min(dp[1][n][0],dp[1][n][1]));}return 0;
}
这篇关于Food Delivery ZOJ - 3469的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
