SRM 602 Div1 Easy TypoCoderDiv1
やりかた
DP。
dp[i][j] :=(i番目までで、レートjの時のレート色の変化した回数の最大値)
(0)次のコンテストが最終コンテストでそれに勝てばbrown coderになれるとき
次コンテストが最終コンテストではないとき
(1)現状がciel coderで次のコンテストで勝ってbrown coderになり、その次のコンテストで負けるとciel coderに戻れる時
(2)現状がciel coderで次のコンテストで勝ってbrown coderになり、その次のコンテストで負けてもciel coderに戻れないとき時
(3)現状がciel coderで次のコンテストで勝ってもbrown coderにはなれないとき
に場合分けして再帰で書いた。常にciel coderでの状態を保持しておく(brown coderは2回連続でなってはいけないためciel coderでの状態のみ意識しておけば十分)。
以下ソース。
int dp[51][2210]; vector<int> R; int N; class TypoCoderDiv1 { public: int rec(int idx, int rate){ if(idx == N) return 0; if(dp[idx][rate] != -1) return dp[idx][rate]; int ret = 0; if(idx + 1 == N){ if(rate + R[idx] >= 2200) // (0) ret = max(ret, 1); }else{ if(rate + R[idx] >= 2200 && rate + R[idx] - R[idx + 1] < 2200) // (1) ret = max(ret, 2 + rec(idx + 2, max(rate + R[idx] - R[idx + 1], 0))); if(rate + R[idx] >= 2200){ // (2) ret = max(ret, rec(idx + 1, max(rate - R[idx], 0))); }else{ //(3) ret = max(ret, rec(idx + 1, rate + R[idx])); ret = max(ret, rec(idx + 1, max(rate - R[idx], 0))); } } return dp[idx][rate] = ret; } int getmax(vector <int> D, int X) { N = D.size(); R = D; memset(dp, -1, sizeof(dp)); return rec(0, X); } };
なんかうまい方法はないかと思ったが思いつかなかった。
Get up! 明日のSUPER ST@R!