題目大意：送餐員送餐問題。有n個人叫餐，每個人都在x軸上，並且每個人都有個坑爹度(和等餐時間有關，據說顧客認為坑爹值到一定程度他的小宇宙就要爆發).現在送餐員從x軸上的某點出發，路上奔跑速度是v，要一次性把所有餐送完。叫餐的人得到餐的時間和順序不同，坑爹度總和也就不同。合格的送餐員要讓客戶體驗最好，請問最少坑爹度和為多少
解題思路：下午開了2011年浙大2月份的月賽，做了三題，這題沒出，被虐暴了。這題要考慮當前狀態對後續狀態的影響，相當經典，很鍛煉思維，這種題目我喜歡。
先說下本題的模型，送餐的順序是一個從x位置開始的從1...n的一個全排列，我們要做的是找一個全排列它的總坑爹值最小。
現在設想已經找到幾個點相對位置是 3 2 1 x 4 5 6,使坑爹值小的策略是先送中間的再往兩邊送，因為送完中間的可以順著去送兩邊。
如果已經計算好了x 1 4的最小坑爹值，如果不考慮坑爹值最小這個條件我們先找2或者5是不是都可以？選了以後對之前的狀態不會影響，因為後面的時間影響不到前面的。得出一個結論，本模型無後效性。
確定了無後效性，那就要考慮那個約束條件和狀態，我們的決策是在x兩邊來回選擇坑爹值小的，那麼設dp[i][j][k]表示從第i個人到第j個人都已經送完餐最後停在k== 0 - 》左邊，k == 1 -》右邊的最小坑爹值。
狀態明確了轉移也就睡到渠成了。dp[i][j][0] 可能從dp[i+1][j][0],dp[i+1][j][1] (i+1在i右邊，兩個都在i左邊)轉移而來，dp[i][j][1]可能從dp[i][j-1][0],dp[i][j-1][1]轉移而來。具體狀態轉移方程參見代碼，很容易看懂。
然後特別要注意的是每轉移一次，都會增加一定的時間，水漲船高，後面的人拿到餐的時間也晚了，也就是說必須把對後面的影響考慮在當前狀態下，並且對後面的每個人影響都是一樣的，那麼當前轉移用時t，後面還有x人，當前的狀態就要多加x*t，
測試數據：
5 1 0
1 1
2 2
3 3
4 4
5 5
C艹代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 1100
#define INF 1100000000
#define min(a,b) ((a)<(b)?(a):(b))
struct node {
int x,v;
}arr[MAX];
int dp[MAX][MAX][2];
int n,v,x,sum[MAX],ans;
int cmp(node a,node b) {
return a.x < b.x;
}
int GetRest(int l,int r) {
if (r < l) return 0;
return sum[r] - sum[l-1];
}
int Solve_Dp() {
int i,j,k,res,delay;
for (i = 1; i <= n; ++i) //找restaurant
if (arr[i].x == x) res = i;
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
dp[i][j][0] = dp[i][j][1] = INF;
dp[res][res][0] = 0;
dp[res][res][1] = 0;
for (i = res; i >= 1; --i)//left
for (j = res; j <= n; ++j) {//right
if (i == j) continue;
//後面的值提前拿出來計算
delay = GetRest(1,i - 1) + GetRest(j + 1,n);
//停在左邊
dp[i][j][0] = min(dp[i][j][0],dp[i+1][j][1]+(delay+arr[i].v)*(arr[j].x-arr[i].x)); //從[i+1,j]右邊來
dp[i][j][0] = min(dp[i][j][0],dp[i+1][j][0]+(delay+arr[i].v)*(arr[i+1].x-arr[i].x));//從[i+1,j]左邊來
//停在右邊
dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][0]+(delay+arr[j].v)*(arr[j].x-arr[i].x)); //從[i,j-1]左邊來
dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][1]+(delay+arr[j].v)*(arr[j].x-arr[j-1].x));//從[i,j-1]右邊來
}
//最後停左邊可以，停右邊也可以
return min(dp[1][n][0],dp[1][n][1]);
}
int main()
{
int i,j,k;
while (scanf("%d%d%d",&n,&v,&x) != EOF) {
for (i = 1; i <= n; ++i)
scanf("%d%d",&arr[i].x,&arr[i].v);
arr[++n].x = x,arr[n].v = 0;
memset(sum,0,sizeof(sum));
sort(arr+1,arr+1+n,cmp); //排序然後按照x將各個坐標分左右兩邊
for (i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + arr[i].v;
ans = Solve_Dp();
printf("%d\n",ans * v); //當算時間的時候是dist/(v^-1)，但是放到最後可以直接乘個v
}
}
