ZOJ3469 Food Delivery 区间DP

题意：有一家快餐店送外卖，现在同时有n个家庭打进电话订购，送货员得以V^-1的速度一家一家的运送，但是每一个家庭都有一个不开心的值，每分钟都会增加一倍，值达到一定程度，该家庭将不会再订购外卖了，现在为了以后有更多的家庭订购，要将外卖送到的情况下使得所有用户的不开心值总和达到最小

思路：区间DP

dp[i][j][0] :表示i到j这段区间内的最小值且留在i点

dp[i][j][1]：表示i到j这段区间内的最小值且留在j点

那么转移方程就是

sum[i]表示1到i的累加和，在枚举i到j的时候（0，i）和（j，n）这两段区间都要加倍

dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(sum[i]+sum[n]-sum[j])*(p[i+1].x-p[i].x));
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(sum[i]+sum[n]-sum[j])*(p[j].x-p[i].x));

dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1])*(p[j].x-p[i].x));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*(p[j].x-p[j-1].x));

 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <algorithm>

 #include <vector>

 #include <map>

 // #include<malloc.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define LL long long

 const int inf = 0x3f3f3f3f;

 const double eps = 1e-;

 // const double pi = acos(-1);

 const LL MOD = ;

 const int N = ;

 // inline int r(){

 //     int x=0,f=1;char ch=getchar();

 //     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}

 //     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

 //     return x*f;

 // }

 struct node{

     int x,y;

 }p[N];

 bool cmp(node a,node b){

     return a.x<b.x;

 }

 int dp[N][N][];

 int sum[N];

 int main(){

     int n,v,x;

     while(~scanf("%d%d%d",&n,&v,&x)){

         for(int i=;i<=n;i++){

             scanf("%d%d",&p[i].x,&p[i].y);

         }

         p[++n].x=x;

         p[n].y=;

         sort(p+,p++n,cmp);

         sum[]=;

         for(int i=;i<=n;i++){

             sum[i]=sum[i-]+p[i].y;

         }

         int tem;

         for(int i=;i<=n;i++){

             if(p[i].x==x){

                 tem=i;

                 break;

             }

         }

         for(int i=;i<=n;i++){

             for(int j=;j<=n;j++){

                 dp[i][j][]=dp[i][j][]=inf;

             }

         }

         dp[tem][tem][]=dp[tem][tem][]=;

         for(int i=tem;i>=;i--){

             for(int j=tem;j<=n;j++){

                 if(i==j) continue;

                 dp[i][j][]=min(dp[i][j][],dp[i+][j][]+(sum[i]+sum[n]-sum[j])*(p[i+].x-p[i].x));

                 dp[i][j][]=min(dp[i][j][],dp[i+][j][]+(sum[i]+sum[n]-sum[j])*(p[j].x-p[i].x));

                 dp[i][j][]=min(dp[i][j][],dp[i][j-][]+(sum[i-]+sum[n]-sum[j-])*(p[j].x-p[i].x));

                 dp[i][j][]=min(dp[i][j][],dp[i][j-][]+(sum[i-]+sum[n]-sum[j-])*(p[j].x-p[j-].x));

             }

         }

         printf("%d\n",v*min(dp[][n][],dp[][n][]));

     }

     return ;

 }

巴特西

ZOJ3469 Food Delivery 区间DP

最新文章

热门文章