問題
http://community.topcoder.com/stat?c=problem_statement&pm=8185
都市ＡとＢがあり、その間の距離があらかじめ与えられる。
またその都市の直線状にならぶ複数のノードがあり、都市Ａを０としたときの距離がが与えられる。
このとき、ノードを全て等間隔にし、ＡとＢをつなぎたい。
ノードを１移動するとコストが１かかり、最大でfunds以内に抑えたい。
このときに必要なノードの間隔の最小値を求める。
解き方
ｄｐを利用する。
ｄｐは現在のノードと現在の距離を状態に持つ、コストの大きさとする。
それぞれの間隔についてコストを計算し、funds以下であるものについて最小のものを求める。
間隔の求め方は昇順に調べてもよいが、2分探索を使って計算量を削減する。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dist,funds,n,dp[110][110];
vector<int> position;
class ConnectTheCities {
public:
int dfs(int v,int len,int width){
if(v==n)return abs(len-dist)<=width ? 0 : 100000;
if(dp[v][len]!=-1)return dp[v][len];
int ret=1e+9;
FORE(i,len,dist+1){
if(abs(i-len)<=width){
ret=min(ret,dfs(v+1,i,width)+abs(i-position[v]));
}
}
return dp[v][len]=ret;
}
int minimalRange(int distance_, int funds, vector<int> position_) {
dist=distance_;
position=position_;
sort(all(position));
n=position.size();
int low=0,high=110;
while(high-low>1){
memset(dp,-1,sizeof(dp));
int mid=(low+high)/2;
int cost=dfs(0,0,mid);
if(cost<=funds)high=mid;
else low=mid;
}
return high;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dist,funds,n,dp[110][110];
vector<int> position;
class ConnectTheCities {
public:
int dfs(int v,int len,int width){
if(v==n)return abs(len-dist)<=width ? 0 : 100000;
if(dp[v][len]!=-1)return dp[v][len];
int ret=1e+9;
FORE(i,len,dist+1){
if(abs(i-len)<=width){
ret=min(ret,dfs(v+1,i,width)+abs(i-position[v]));
}
}
return dp[v][len]=ret;
}
int minimalRange(int distance_, int funds, vector<int> position_) {
dist=distance_;
position=position_;
sort(all(position));
n=position.size();
int low=0,high=110;
while(high-low>1){
memset(dp,-1,sizeof(dp));
int mid=(low+high)/2;
int cost=dfs(0,0,mid);
if(cost<=funds)high=mid;
else low=mid;
}
return high;
}
};