生活随笔
收集整理的这篇文章主要介绍了
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));
1 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <iostream>
6 #include <queue>
7 #include <stack>
8 #include <cmath>
9 #include <
set>
10 #include <algorithm>
11 #include <vector>
12 #include <map>
13 // #include<malloc.h>
14 using namespace std;
15 #define clc(a,b) memset(a,b,sizeof(a))
16 #define LL long long
17 const int inf =
0x3f3f3f3f;
18 const double eps = 1e-
5;
19 // const double pi = acos(-1);
20 const LL MOD =
9901;
21 const int N =
1010;
22
23 // inline int r(){
24 // int x=0,f=1;char ch=getchar();
25 // while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
26 // while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
27 // return x*f;
28 // }
29 struct node{
30 int x,y;
31 }p[N];
32
33
34 bool cmp(node a,node b){
35 return a.x<
b.x;
36 }
37
38 int dp[N][N][
2];
39 int sum[N];
40
41 int main(){
42 int n,v,x;
43 while(~scanf(
"%d%d%d",&n,&v,&
x)){
44 for(
int i=
1;i<=n;i++
){
45 scanf(
"%d%d",&p[i].x,&
p[i].y);
46 }
47 p[++n].x=
x;
48 p[n].y=
0;
49 sort(p+
1,p+
1+
n,cmp);
50
51 sum[
0]=
0;
52 for(
int i=
1;i<=n;i++
){
53 sum[i]=sum[i-
1]+
p[i].y;
54 }
55 int tem;
56 for(
int i=
1;i<=n;i++
){
57 if(p[i].x==
x){
58 tem=
i;
59 break;
60 }
61 }
62
63 for(
int i=
0;i<=n;i++
){
64 for(
int j=
0;j<=n;j++
){
65 dp[i][j][
0]=dp[i][j][
1]=
inf;
66 }
67 }
68 dp[tem][tem][
1]=dp[tem][tem][
0]=
0;
69
70 for(
int i=tem;i>=
1;i--
){
71 for(
int j=tem;j<=n;j++
){
72 if(i==j)
continue;
73
74 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));
75 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));
76
77 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));
78 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));
79 }
80 }
81 printf(
"%d\n",v*min(dp[
1][n][
0],dp[
1][n][
1]));
82 }
83 return 0;
84 }
转载于:https://www.cnblogs.com/ITUPC/p/5502284.html
总结
以上是生活随笔为你收集整理的ZOJ3469 Food Delivery 区间DP的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
