SRM 462 Div2 Hard SteeplechaseTrack

問題

馬がフェンスを飛び越えてコースを走りまわるレースが行われる。あなたはこのレースを出来るだけ難しい物にしたい。
vector< string > fenceが与えられ、各string の最初の1文字がスタート地点からそのフェンス手前に行くまでの難しさ、次の1文字がそのフェンスをジャンプして越える難しさ、次の1文字がそのフェンス後ろからゴール地点にたどり着くための難しさを表す。もし'0'の場合はそこを通れないものとする。
加えて、vector< string > tracksが与えられ、tracks[i][j]はフェンスi後ろからフェンスj手前に行くまでの難しさを表す。もし'0'の場合はそこを通れないものとする。
フェンス手前まで行った場合は必ずフェンスを飛び越えねばならない。レースコースの全体の難しさとは、これらの難しさの合計である。フェンスを飛ぶ回数をK回以内に制限した場合、もっとも難しくなるようなレースコースの難しさを求めよ。ゴールに到達不可能の場合は-1を返せ。

やりかた

典型的なDP。
dp[i][k] :=（フェンスi後ろの地点にk回のジャンプの後にたどり着くような最大値）
とすると、

                   //フェンスiから道i->jを通り、フェンスjを飛び越すコスト
dp[j][k + 1] = max(dp[i][k] + tracks[i][j] - '0' + fences[j][0] - '0')

と更新できる。dp[i][j]の状態に辿りつけなかったり、iからlへの道がない場合などには更新しないようにする。また、スタート地点からフェンス手前に行けなかったり、フェンス後ろからゴールまで行けない時なども更新しないようにする。

以下ソース。

int dp[51][101];

class SteeplechaseTrack {
public:
  int maxComplexity(vector <string> fences, vector <string> tracks, int K) {
    int N = fences.size();
    
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < N; i++)
      if(fences[i][1] != '0')
	dp[i][1] = fences[i][1] - '0' + fences[i][0] - '0';

    for(int k = 1; k < K; k++)
      for(int i = 0; i < N; i++)
	for(int j = 0; j < N; j++)
	  if(tracks[i][j] != '0' && dp[i][k] != 0)
	    dp[j][k + 1] = max(dp[j][k + 1], 
			       dp[i][k] + tracks[i][j] - '0' + fences[j][0] - '0');
    int ret = -1;
    for(int k = 1; k <= K; k++)
      for(int i = 0; i < N; i++)
	if(dp[i][k] != 0 && fences[i][2] != 0)
	  ret = max(ret, dp[i][k] + fences[i][2] - '0');
    return ret;
  }
};

2周目できちんと出来た。よかった。