TopCoder SRM 492 SRM Div1 Medium TimeTravellingTour
問題
N個の都市がいくつかの道でつながっている。
それぞれの道がどの都市をつなぎ、どれくらいの長さであるかが与えられる。
Gogoはcities[i]で表される都市を全て訪問したい。
cities[i]の都市はこの順に訪問する必要がある。(ただし、別の都市の通り道として、訪問せずに経由することもできる)
また、Gogoはタイムマシーンを持っていて、今までに通った都市に時間0で戻ることができる。
ただし、タイムマシーンで一度戻った後で、逆方向にタイムマシーンを使うことはできない。すなわち、A,B,C,D,Eと都市を通り、タイムマシーンでCに戻った後はタイムマシーンでDやEへ行くことはできない。(AやBへ行くことは可能)
このとき、全ての都市を訪問するのにかかる時間を求めよ。
都市の訪問を終了したとき、Gogoはどの都市にいてもよいものとする。
制約条件
N≦50
訪問する都市の数≦50
方針
動的計画法による。
dp[i][l][r]を、現在都市iにいて、訪問リストのj番目の都市からk番目の都市を全て訪問するのにかかる時間とする。
すると、dp[i][l][r]は、iからcities[l]へ行って、l+1からrを訪問する仕方と、
都市jまで一旦行き、リストのm(j≦m≦k)番目の都市mへ行って、jまでタイムマシンで戻り、jからm+1番目の都市からr番目の都市まで訪問する仕方の二つに分けられる。
それぞれの場合は、より小さい部分問題になっているため、
これをメモ化して更新していくようなO(N^5)の動的計画法により解ける。
定数倍がやや厳しく、再帰で書くとTLEした。
ソースコード
ll dp[50][51][51]; ll d[50][50]; class TimeTravellingTour { public: long long determineCost(int N, vector <int> C, vector <string> roads) { rep(i,N)rep(j,N)d[i][j]=i==j?0:INF; string s=accumulate(all(roads),string()); rep(i,s.size())if(s[i]==',')s[i]=' '; stringstream ss(s); int a,b,c; while(ss>>a>>b>>c)d[a][b]=d[b][a]=c; rep(k,N)rep(i,N)rep(j,N)d[i][j]=min(d[i][j],d[i][k]+d[k][j]); int m=C.size(); rep(i,N)rep(j,m+1)rep(k,m+1)dp[i][j][k]=j>k?0:INF; rep(i,N)rep(j,m)dp[i][j][j]=d[i][C[j]]; for(int s=2;s<=m;s++)rep(i,N)rep(l,m-s+1){ int r=l+s-1; if(i==C[l]){ dp[i][l][r]=dp[i][l+1][r]; continue; } dp[i][l][r]=dp[C[l]][l+1][r]+d[i][C[l]]; for(int m=l;m<r;m++)rep(j,N) dp[i][l][r]=min(dp[i][l][r],d[i][j]+dp[j][l][m]+dp[j][m+1][r]); } return dp[0][0][m-1]>=INF?-1:dp[0][0][m-1]; } };