Food Delivery
Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %lld & %llu
SubmitStatus
Description
When we are focusing on solving problems, we usually prefer to stay in front of computers rather than go out for lunch. At this time, we may call for food delivery.
Suppose there are N people living in a straight street that is just lies on an X-coordinate axis. Theith person’s coordinate is Xi meters. And in the street there is a take-out restaurant which has coordinatesX meters. One day at lunchtime, each person takes an order from the restaurant at the same time. As a worker in the restaurant, you need to start from the restaurant, send food to theN people, and then come back to the restaurant. Your speed is V-1 meters per minute.
You know that the N people have different personal characters; therefore they have different feeling on the time their food arrives. Their feelings are measured byDispleasure Index. At the beginning, the Displeasure Index for each person is 0. When waiting for the food, theith person will gain BiDispleasure Index per minute.
If one’s Displeasure Index goes too high, he will not buy your food any more. So you need to keep the sum of all people’sDispleasure Index as low as possible in order to maximize your income. Your task is to find the minimal sum ofDispleasure Index.
Input
The input contains multiple test cases, separated with a blank line. Each case is started with three integersN ( 1 <= N <= 1000 ), V ( V > 0), X (X >= 0 ), then N lines followed. Each line contains two integersXi ( Xi >= 0 ), Bi ( Bi >= 0), which are described above.
You can safely assume that all numbers in the input and output will be less than 231 – 1.
Please process to the end-of-file.
Output
For each test case please output a single number, which is the minimal sum ofDispleasure Index. One test case per line.
Sample Input
5 1 01 12 23 34 45 5
Sample Output
55
题意：在X-轴上有一个餐厅，以及有n个点要送外卖。餐厅坐标为x，工人的速度为V-1，也就是 1/v 米每分钟（不是v米每分钟）。给出n的点的x坐标和参数v，外卖没送到，客户就会不愉快，每一分钟的不愉快指数增加v。问怎么样的送货策略，使得所有客户的总不愉悦指数和最小。
思路：区间DP。用一个数组 dp 维护。
DP的思路就是，如果要访问完 [i, j] ，，那么它的子区间一定访问完了。
dp[i][j][0] 表示当前 [ i, j ] 区间内已经全部送餐完毕，并且这个时刻工人位于区间左端，也就是坐标 i
dp[i][j][1] 表示当前 [ i, j ] 区间内已经全部送餐完毕，并且这个时刻工人位于区间又端，也就是坐标 j
状态转移方程：
以餐厅的位置 pos 为中间点，i 在餐厅pos位置的左边，j 在餐厅pos位置的右边。
dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][0]+(a[i+1].x-a[i].x)*(delay+a[i].v));
这个方程里面，delay 表示区间 [i，j] 之外的所有点的v值之和，a[i+1].x-a[i].x 表示距离，dp[i+1][j][0]是已经求出来的子区间，加上(a[i+1].x-a[i].x)*(delay+a[i].v))，就得到 dp[i][j][0]。
#include <cstdio>#include <iostream>#include <cstring>#include <cmath>#include <string>#include <algorithm>#include <queue>#include <stack>using namespace std;const int INF = 1<<29;const double PI = acos(-1.0);const double e = 2.718281828459;const double eps = 1e-8;const int MAXN = 1010;int dp[MAXN][MAXN][2];int sum[MAXN];struct node{int x;int v;} a[MAXN];int cmp(node x, node y){return x.x < y.x;}int Delay(int l, int r){if(l > r)return 0;return sum[r]-sum[l-1];}int main(){//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int n, v, x;while(scanf("%d %d %d", &n, &v, &x) != EOF){for(int i = 1; i <= n; i++)scanf("%d %d", &a[i].x, &a[i].v);n++;a[n].x = x;a[n].v = 0;sort(a+1, a+1+n, cmp);sum[0] = 0;for(int i = 1; i <= n; i++)sum[i] = sum[i-1]+a[i].v;int pos = 1;for(int i = 1; i <= n; i++){if(a[i].x == x){pos = i;//cout<<pos<<endl;break;}}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){dp[i][j][0] = dp[i][j][1] = INF;}}dp[pos][pos][0] = dp[pos][pos][1] = 0;for(int i = pos; i >= 1; i–){//i循环pos左边for(int j = pos; j <= n; j++){//j循环pos右边int delay = Delay(1, i-1)+Delay(j+1, n);if(i == j)continue;dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][0]+(a[i+1].x-a[i].x)*(delay+a[i].v));dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][1]+(a[j].x-a[i].x)*(delay+a[i].v));dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][0]+(a[j].x-a[i].x)*(delay+a[j].v));dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][1]+(a[j].x-a[j-1].x)*(delay+a[j].v));}}printf("%d\n", min(dp[1][n][0], dp[1][n][1])*v);//本题的v一定要留到后面来乘，中间DP的时候乘可能会溢出，导致wa }return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
看着它或是汹涌或是平静，然而一直相随，不离不弃。
