SRM 553 Div2 Hard SafeRemoval

問題

数列が与えられる。この数列から１つずつ数字を取り除きたい。数字を取り除くとき、残りの数列の和が４の倍数にならないように取り除く。このようにしてK個の数字を取り除くとき、残った数列の和が最大になるようにしたい。最大値を求めよ。

やりかた

Editorialを参考にしました。

DP。数列の数字を4で割ったあまりで書く数字を区別する。
dp[i][j][k][l] := （
数列の小さい方から
4で割ったあまりが0の数字をi個使用、
4で割ったあまりが0の数字をj個使用、
4で割ったあまりが0の数字をk個使用、
4で割ったあまりが0の数字をl個使用 しているとき数列和の最大値。
）

まず数列をソートし、４で割ったあまりで振り分けていく。
そして数列和が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の調子悪いなあ。