SRM602 Div1 Easy "TypoCoderDiv1"
問題
TopCoder Statistics - Problem Statement
訳
TypeCoderはTopCoderに似たプログラミングコンテストである。TypeCoderもまたレーティングシステムを採用している。TypoCoderにはbrown coderとciel coderの2つの種類がある。brown coderはレーティングが2200以上のコーダーをいう。ciel coderはレーティングが2200に満たないコーダーをいう。
猫のロワーはTypoCoderのコーダーである。彼は現在ciel coderである。彼のレーティングは今年はXで終えた。
来年、いくつかのコンテストが開催される。各コンテストでロワーはベストを尽くすか、わざと負けるか選択することができる。i回目のコンテスト(0-base)の重要さはD[i]である。もしロワーがi回目のコンテストでベストを尽くせば、彼のレーティングはD[i]上がる。もしわざと負ければ、彼のレーティングはD[i]下がる。ただし、0を下回ることはない。正確には、彼のレーティングはmin(D[i],コンテストを受けたときのレーティング)だけ下がる。
ロワーはciel coderであることに誇りを持っている。よって、彼は2回続けてbrown coderになることは我慢ならなかった。つまり、彼がbrown coderになる度に次のコンテストの後で再びciel coderになる必要がある(次回コンテストがあれば)。
TypoCoderは1年間で最も色が変わったコーダーに対し、"カメレオンコーダー・オブ・ザ・イヤー"として表彰する。
あなたはint[] Dとint Xが与えられる。ロワーが来年、最大で何回色を変えられるかを返せ。
制約
1 <= コンテストの回数 <= 50
0 <= D[i] <= 10^9
0 <= X <= 2199
考えたこと
うーむ・・D[i]が最大10^9とな・・・
DPっぽいが、レーティングを状態として持つわけにいかんか←思考の罠
ここは何回目のコンテストで、何回色が変わったときの、レーティングの最大最小を持つ・・・とか?
・・・
だめだ、できね・・
・・・
あ、これ連続でbrown coderになれないから、色が2回一気に変わると考えれば、レーティングは0~2199まで持てばよさそうだ!
dp[i][j] := i回目のコンテスト開始時で、レーティングがjだったときの、最大の色変化数。
初期化はdp[0][X] = 0 (他は-1)
更新は
☆わざと負ける
⇒レーティングダウン
☆最後のコンテストの場合
⇒ベストを尽くして2200超えるようなら+1
☆ベストを尽くしても2200を超えない場合
⇒レーティングアップ
☆ベストを尽くしたら2200を超えて、かつ次のコンテストで2200を下回る場合
⇒2回分一気に計算して、+2
結果はdp[コンテストの回数][j]の最大値
int dp[55][2250]; class TypoCoderDiv1 { public: int getmax(vector <int> D, int X) { int N = D.size(); memset(dp, -1, sizeof(dp)); // dp初期化 dp[0][X] = 0; // dp更新 for (int i = 0; i < N; i++) { for (int j = 0; j < 2200; j++) { if (dp[i][j] == -1) continue; // lose int nj = max(0, j - D[i]); dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j]); // best if (i == N - 1) { // last if (j + D[i] >= 2200) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1); } else if (j + D[i] < 2200){ // rate up nj = j + D[i]; dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j]); } else { nj = max(0, j + D[i] - D[i + 1]); // +2 if (nj < 2200) dp[i + 2][nj] = max(dp[i + 2][nj], dp[i][j] + 2); } } } // 結果集計 int res = 0; for (int i = 0; i < 2200; i++) { res = max(res, dp[N][i]); } return res; } };