TopCoder SRM 602 Div1 Easy TypoCoderDiv1

問題

Typocoderにn回参加する。
初期のレーティングはXで、i回目のコンテストで本気を出すとD[i]レーティングが上がり、
本気を出さないとD[i]レーティングが下がる。
ただし、レーティングが0未満になったときは、0になるとする。

レーティングが2200以上の人はbrown coderで、
2200未満の人はciel coderである。

コンテスト終了時にbrown coderであることが２回連続しないようにしたい。
（n回のコンテスト終了時にbrownになっていてもよい）
この条件の下で、色が変化する回数を最も増やしたい。
回数の最大値を求めよ。

制約条件

n≦50
D[i]≦10億
X≦2200

方針

D[i]が小さかったらdp[コンテスト何回やったか][レート]:=色変化の回数の最大値
みたいなDPが出来るが、D[i]が大きい。

けれどよく考えると、一度2200を超えても次のコンテストでは2200未満になるので、
色が変化するときは二回の動きをまとめて処理すれば結局2200未満のレートの部分だけを覚えるDPが出来る。

ソースコード

int dp[51][2300];

class TypoCoderDiv1 {
	public:
	int getmax(vector <int> D, int X) {
		int n = D.size();
		int ans = 0;
		memset(dp, -1, sizeof(dp));
		dp[0][X] = 0;
		
		rep(i, n){
			rep(j, 2300) if(dp[i][j] >= 0){
				if(j + D[i] >= 2200){
					if(i == n - 1) ans = max(ans, dp[i][j] + 1);
					else if(j + D[i] - D[i + 1] < 2200){
						int nj = max(0, j + D[i] - D[i + 1]);
						dp[i + 2][nj] = max(dp[i + 2][nj], dp[i][j] + 2);
					}
				}
				else dp[i + 1][j+ D[i]] = max(dp[i + 1][j + D[i]], dp[i][j]);
				dp[i + 1][max(0, j - D[i])] = max(dp[i + 1][max(0, j - D[i])], dp[i][j]);
			}
		}
		rep(i, 2300) ans = max(ans, dp[n][i]);
		return ans;
	}
};