SRM602 div1 Easy TypoCoderDiv1

メモ

動的計画法。

dp[i+1][j] := i個目まででレートがjの時の色が変わった回数の最大値とする。レートjにならない時は-1とする。

レートは10⁹以上になるため工夫しないとTLE。

2200以上が2回以上続くことが禁止されているため、2200未満のレートだけ考えれば大丈夫。

dp[i][j] >= 0の時、次の3つの状態推移が考えられる、「下げる」、「上げても2200未満」、「上げて2200以上で下げて2200未満になる」。

コード

class  TypoCoderDiv1{
  public:
  int getmax(vector <int> D, int X) {
    int n = D.size();
    int dp[n+1][2200];
    memset(dp, -1, sizeof(dp));
    dp[0][X] = 0;
    FOR(i,0,n) {
      FOR(j,0,2200) {
        if(dp[i][j] != -1) {
          // 下がる
          dp[i+1][max(0, j-D[i])] = max(dp[i+1][max(0, j-D[i])], dp[i][j]);
          // 上がる
          if(j + D[i] < 2200) {
            dp[i+1][j+D[i]] = max(dp[i+1][j+D[i]], dp[i][j]);
          }
          // 上がる下がる
          if(i + 2 <= n && j + D[i] >= 2200 && j + D[i] - D[i+1] < 2200) {
            dp[i+2][max(0, j+D[i]-D[i+1])] = max(dp[i+2][max(0, j+D[i]-D[i+1])], dp[i][j] + 2);
          }
        } 
      }
    }
    int ans = 0;
    FOR(i,0,2200) ans = max(ans, dp[n][i]);
    FOR(i,0,2200) {
      if(i+D[n-1] >= 2200) {
        ans = max(ans, dp[n-1][i]+1);
      }
    }
    return ans;
  }
};