 /**//*
一條直線上,一家餐廳在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;
}

|