SRM 553 Div2 Hard SafeRemoval
問題
数列が与えられる。この数列から1つずつ数字を取り除きたい。数字を取り除くとき、残りの数列の和が4の倍数にならないように取り除く。このようにしてK個の数字を取り除くとき、残った数列の和が最大になるようにしたい。最大値を求めよ。
やりかた
Editorialを参考にしました。
DP。数列の数字を4で割ったあまりで書く数字を区別する。
dp[i][j][k][l] := (
数列の小さい方から
4で割ったあまりが0の数字をi個使用、
4で割ったあまりが0の数字をj個使用、
4で割ったあまりが0の数字をk個使用、
4で割ったあまりが0の数字をl個使用 しているとき数列和の最大値。
)
まず数列をソートし、4で割ったあまりで振り分けていく。
そして数列和が4の倍数にならないようにDPを更新していき、数列の個数がN - Kになったときに4の倍数になっていなければそれが答え。
数列から取り除いていくと言うよりも数列を構成していくというイメージ。
int dp[51][51][51][51]; class SafeRemoval { public: int removeThem(vector <int> seq, int k) { memset(dp, 0, sizeof(dp)); int N = seq.size(); sort(ALL(seq), greater<int>()); int a[4][51];//4で割ったあまりを振り分けて入れる int b[4][51];//aの累積和を記録していく for(int i = 0; i < 4; i++) a[i][0] = b[i][0] = 0; for(int i = 0; i < N; i++){ int mod = seq[i] % 4; a[mod][++a[mod][0]] = seq[i]; b[mod][a[mod][0]] = seq[i] + b[mod][a[mod][0] - 1]; } for(int i0 = 0; i0 <= a[0][0]; i0++) for(int i1 = 0; i1 <= a[1][0]; i1++) for(int i2 = 0; i2 <= a[2][0]; i2++) for(int i3 = 0; i3 <= a[3][0]; i3++){ if(i0 + i1 + i2 + i3 < N - k) continue; //数列の個数がN - Kになったとき if(i0 + i1 + i2 + i3参考にしました。 == N - k){ dp[i0][i1][i2][i3] = b[0][i0] + b[1][i1] + b[2][i2] + b[3][i3]; if(dp[i0][i1][i2][i3] % 4 == 0) dp[i0][i1][i2][i3] = -1; }else{ dp[i0][i1][i2][i3] = -1; if((b[0][i0] + b[1][i1] + b[2][i2] + b[3][i3]) % 4 != 0){ if(i0 > 0 && dp[i0][i1][i2][i3] < dp[i0 - 1][i1][i2][i3]) dp[i0][i1][i2][i3] = dp[i0 - 1][i1][i2][i3]; if(i1 > 0 && dp[i0][i1][i2][i3] < dp[i0][i1 - 1][i2][i3]) dp[i0][i1][i2][i3] = dp[i0][i1 - 1][i2][i3]; if(i2 > 0 && dp[i0][i1][i2][i3] < dp[i0][i1][i2 - 1][i3]) dp[i0][i1][i2][i3] = dp[i0][i1][i2 - 1][i3]; if(i3 > 0 && dp[i0][i1][i2][i3] < dp[i0][i1][i2][i3 - 1]) dp[i0][i1][i2][i3] = dp[i0][i1][i2][i3 - 1]; } } } return dp[a[0][0]][a[1][0]][a[2][0]][a[3][0]]; } };
SRMの調子悪いなあ。
Get up! 明日のSUPER ST@R!