TopCoder SRM 370 Div1 Medium ConnectTheCities

問題概要

直線で結ばれた二つの都市A,Bの間に中継点がいくつかある。
中継点は動かすことができて、一つを1単位動かすのに1単位のコストがかかる。
ただし、中継点が移動できるのは左右の方向に、整数距離だけである。

各中継点の座標と、支払える最大コストが与えられたとき、「となりあう中継地点間の最大距離」を最小にするように中継点を動かしたときの「最大距離」を求めよ。
（都市A,Bは両端にある動かせない点と考える）

解法

i個目の中継点をjに置き、それまでの最大距離がkのときにかかる最小コストをdp[i][j][k]と置いて動的計画法のアルゴリズムを用いればよい。

右端の中継点の置き方全て(dp[n-1][0][0]からdp[n-1][d][d])に対して、支払えるコスト以下のもので最大距離が最小のものを探せば、それが答えである。

中継点の初期座標をソートすることを忘れずに。（はまった）

ソースコード

int dp[50][101][101];

class ConnectTheCities {
	public:
	int minimalRange(int d, int funds, vector <int> pos) 
	{
		int n=pos.size();
		sort(all(pos));
		
		rep(i,n)rep(j,d+1)fill_n(dp[i][j],101,inf);
		
		rep(i,d+1)dp[0][i][i]=abs(pos[0]-i);
		for(int i=0;i<n-1;i++)for(int j=0;j<=d;j++)for(int k=0;k<=d;k++)
		if(dp[i][j][k]!=inf)
		{
			for(int l=j;l<=d;l++)
			{
				dp[i+1][l][max(k,l-j)]=min(dp[i+1][l][max(k,l-j)],
					dp[i][j][k]+abs(pos[i+1]-l)
				);
			}
		}
		
		int ans=inf;
		rep(j,d+1)rep(k,d+1)if(dp[n-1][j][k]<=funds)
		{
			ans=min(ans,max(d-j,k));
		}
		return ans;
	}
};