TopCoder SRM 602 Div1 Easy TypoCoderDiv1

今年最後のSRM、550ptMediumを解ききってかなりの好順位で締めることができた。
おかげでレートもギリギリ自己ベスト更新。
Easyはちょっと時間かけすぎたな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12924

問題

参加者の初期状態のレートXと、コンテストごとのレート変動量D[i]が与えられる。
コンテストはDの順番で開催され、i番目のコンテストに参加すると、自分のレートはD[i]加算するか減算するかどちらかである。(ただしレート最小値は0)

レートが2199と2200の間をまたぐと参加者の色が変わる。
なお、参加者は２期連続2200を超えていてはならない。

色が変わる回数を最大化せよ。

解法

現在のレート0～2199を状態として、色が変わる回数をDPで求めていく。
各レートについてD[i]を加算または減算した状態についてDPすればよい。
ただし、D[i]を加算することでレートが2200を超える場合、D[i+1]を減算して2200未満にならなければいけない。

int dpdp[55][2300];

class TypoCoderDiv1 {
	public:
	int getmax(vector <int> D, int X) {
		int i,x,y,j;
		int L=D.size();
		
		FOR(i,L+1) FOR(x,2300) dpdp[i][x]=-999999;
		dpdp[0][X]=0;
		
		FOR(i,L) FOR(x,2200) {
			if(dpdp[i][x]<0) continue;
			
			dpdp[i+1][max(0,x-D[i])] = max(dpdp[i+1][max(0,x-D[i])], dpdp[i][x]);
			
			ll af=x+D[i];
			if(af<2200) {
				dpdp[i+1][af] = max(dpdp[i+1][af], dpdp[i][x]);
			}
			else {
				if(i+1<L) {
					af=max(0LL,af-D[i+1]);
					if(af<2200) dpdp[i+2][af] = max(dpdp[i+2][af], dpdp[i][x]+2);
				}
				else {
					dpdp[L][2200] = max(dpdp[L][2200], dpdp[i][x]+1);
				}
			}
		}
		int r=0;
		FOR(i,2201) r=max(r,dpdp[L][i]);
		return r;
	}
};

まとめ

１回で1000000000もレートが上がるなんて羨ましいですね。