zoj 3469 Food Delivery 题意：有一家快餐店送外卖，现在同时有n个家庭打进电话订购，送货员得以1/V（输入的值就是1/V）的速度一家一家的运送，但是每一个家庭都有一个不开心的值，每分钟都会增加一倍，值达到一定程度，该家庭将不会再订购外卖了，现在为了以后有更多的家庭订购，要将外卖送到的情况下使得所有用户的不开心值总和达到最小； 思路：将所有的点排序（包括餐馆），排序后从餐馆的位置开始dp； dp[i][j][0]表示从i到j用户送到最小不开心值，此时送货员停留在左边即i位置 dp[i][j][1]表示从i到j用户送到最小不开心值，此时送货员停留在右边即j位置 dp[i][j][0]可以通过dp[i+1][j][0]和dp[i+1][j][1]到达； dp[i][j][1]可以通过dp[i][j-1][1]和dp[i][j-1][0]到达； 但是要加上其他点的愤怒值即：终止点到起始点的距离差*（终止点愤怒值+i，j外的其余点愤怒值之和）；本来是计算时间要除1/V即乘V，可以改到最后再乘；
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int inf=0x3f3f3f3f;struct zp{ int id,w;} node[100010];int sum[100010],dp[1010][1010][2];int cmp(zp a,zp b){ return a.id<b.id;}int judge(int i,int j){ if(i>j) return 0; return sum[j]-sum[i-1];}int main(){ int n,m,v; while(~scanf("%d%d%d",&n,&v,&m)) { memset(sum,0,sizeof(sum)); memset(dp,inf,sizeof(dp)); for(int i=1; i<=n; i++) scanf("%d%d",&node[i].id,&node[i].w); node[++n].id=m,node[n].w=0;//加入起点 sort(node+1,node+n+1,cmp); for(int i=1; i<=n; i++)//统计愤怒值的前缀和，方便计算 sum[i]=sum[i-1]+node[i].w; int star=0; for(int i=1; i<=n; i++)//找起始点 if(node[i].id==m) { star=i; break; } dp[star][star][0]=dp[star][star][1]=0; for(int i=star; i>0; i--)//起点左边 { for(int j=star; j<=n; j++)//起点右边 { int tmp=judge(1,i-1)+judge(j+1,n);//i，j区间外的其他点的不开心值的和 if(i==j) continue; //下面是距离差 //下面愤怒值之和 dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(node[i+1].id-node[i].id)*(tmp+node[i].w)); dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(node[j].id-node[i].id)*(tmp+node[i].w)); dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(node[j].id-node[i].id)*(tmp+node[j].w)); dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(node[j].id-node[j-1].id)*(tmp+node[j].w)); } } PRintf("%d/n",min(dp[1][n][0],dp[1][n][1])*v);//记住*V }}新闻热点
疑难解答
