/**//* 一条直线上,一家餐厅在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; }
|