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)); } }新聞熱點
疑難解答
