SRM 602 Div1 Easy TypoCoderDiv1

やりかた

DP。
dp[i][j] :=（i番目までで、レートjの時のレート色の変化した回数の最大値）

（０）次のコンテストが最終コンテストでそれに勝てばbrown coderになれるとき

次コンテストが最終コンテストではないとき
（１）現状がciel coderで次のコンテストで勝ってbrown coderになり、その次のコンテストで負けるとciel coderに戻れる時
（２）現状がciel coderで次のコンテストで勝ってbrown coderになり、その次のコンテストで負けてもciel coderに戻れないとき時
（３）現状が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);
  }
};

なんかうまい方法はないかと思ったが思いつかなかった。