 /**//*
一条直线上,一家餐厅在X,n个客人,第i个在xi
一个服务员的速度为1/v , 客人i的不满意度为等待时间Ti*Bi
求 minimal ∑不满意度
容易知道最优的路线是左右来回走,一直到所有客人都访问完
设X左边有nl个,右边有nr个
dp[l,r,0/1]表示[l,r]已经访问完了,目前在左、右边的最优值
转移时枚举邻近的一个
如dp[l,r,0] 由dp[l-1,r,0],dp[l-1,r,1] 因为l是由邻近的l-1走过来的!!
若dp[l,r,0]存的仅仅是[l,r]的代价的话,转移就不知道怎么算了
因为从[l-1,r]转移到[l,r,0]时,不知道到l的总时间,而dp值又没有存时间
我困惑在dp应该存 题目定义的花费?还是时间?还是两者都存?
看了watashi的做法
dp[l,r]的值存的不仅是[l,r]的代价,还包括这段时间内[l,r]之外的点应该计算的代价!!!
这样子总的代价就能算了
代价放到前面去计算,应该用得比较多吧?
poj 1180也是代价放到前面算好一部分

*/

#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<functional>

using namespace std;

const int INF = 1000000000;

vector<pair<int,int> > vl , vr;
int dp[1010][1010][2];

 int memo(int l , int r , int p) {
 if(dp[l][r][p] == -1) {
int &ans = dp[l][r][p];
ans = INF;
 if(p==0) {
 if(l) {
int sumCost = (vl[l].second+vr[r+1].second);//还包括[l,r]外面的代价值,预先累计
ans = min(ans , memo(l-1,r,0) + (vl[l-1].first - vl[l].first)*sumCost);
ans = min(ans , memo(l-1,r,1) + (vr[r].first - vl[l].first)*sumCost);
}
}
 else {
 if(r) {
int sumCost = (vl[l+1].second+vr[r].second);
ans = min(ans , memo(l,r-1,0) + (vr[r].first - vl[l].first)*sumCost);
ans = min(ans , memo(l,r-1,1) + (vr[r].first - vr[r-1].first)*sumCost);
}
}
}
return dp[l][r][p];
}

int main()
  {
 for(int n , v , x ; ~scanf("%d%d%d",&n,&v,&x);) {//题目的v不是速度,是速度的倒数
vl.clear();
vr.clear();
 for(int i = 0,xi,bi; i < n ; i ++) {
scanf("%d%d",&xi,&bi);
 if(xi<x) {
vl.push_back(make_pair(xi-x,bi));
}
 else {
vr.push_back(make_pair(xi-x,bi));
}
}
vl.push_back(make_pair(0,0));
vr.push_back(make_pair(0,0));
sort(vl.begin(),vl.end(),greater<pair<int,int> >() );
sort(vr.begin(),vr.end());
int nl = vl.size() - 1;
int nr = vr.size() - 1;
 for(int i = nl - 1 ; i > 0 ; i--) {//vl[i]存的是[i,nl]的值
vl[i].second += vl[i+1].second;
}
vl.push_back(make_pair(-INF,0));
 for(int i = nr - 1 ; i > 0 ; i --) {//vr[i]存的是[i,nr]的值
vr[i].second += vr[i+1].second;
}
vr.push_back(make_pair(INF,0));
for(int i = 0 ; i <= nl ; i++)
for(int j = 0 ; j <= nr; j++)
dp[i][j][0] = dp[i][j][1] = -1;
dp[0][0][0] = dp[0][0][1] = 0;
printf("%d\n",v*min(memo(nl,nr,0),memo(nl,nr,1)));
}
return 0;
}

|