SRM 694 Div1 easy : TrySail

問題概要 :
n人の生徒からなるクラスがある.
各生徒には強さがあり、それらは0以上255以下の整数として表される.

n人の生徒を3つのグループに分ける.
ただし、グループ分けを行う際に、だれも生徒が属さないようなグループが出来てはいけない.
グループの強さはそのグループに属する生徒の強さのbitwise xorをとった値とする.
このとき、3つのグループの強さの総和を最大化し、その値を返せ.

制約 :
3 <= n <= 50
0 <= 生徒の強さ <= 255

解法 :
制約を見てみると強さも生徒数も少ないので、そのまま配列を確保してDPする.

3つのグループには1から順に3まで番号が割り振られているものとする.

dp[i][j][k][l] := グループ3の最大値
i : 各グループに生徒を1人以上割り当てたかどうかをビットで表す ( 0 <= i < (1<<3) )
j : グループ1の現在の強さ ( 0 <= j < (1<<8) )
k : グループ2の現在の強さ ( 0 <= k < (1<<8) )
l : curとnext ( 0 <= l < 2 )

他の人のコードを見てみると2次元配列で解いていた人もいたでのメモリ節約できるらしい

コード :

#define MAX (1<<8)
  int dp[10][MAX][MAX][2];
  
  class TrySail {
  public:
    int get(vector <int> vec) {
      memset(dp,-1,sizeof dp);
      int n = (int)vec.size();
      dp[0][0][0][0] = 0;

      rep(i,n) {
	int cur  = i & 1;
	int next = (i+1) & 1;
	{
	  rep(j,(1<<3)) rep(k,MAX) rep(l,MAX) dp[j][k][l][next] = -1;
	}
	rep(bit,(1<<3)) {
	  rep(p1,MAX) {
	    rep(p2,MAX) {
	      if( dp[bit][p1][p2][cur] == -1 ) continue;
	      rep(sel,3) {
		int nbit = bit | (1<<sel);
		int np1 = p1;
		int np2 = p2;
		int np3 = dp[bit][p1][p2][cur];
		if( sel == 0 ) np1 = np1 ^ vec[i];
		if( sel == 1 ) np2 = np2 ^ vec[i];
		if( sel == 2 ) np3 = np3 ^ vec[i];
		dp[nbit][np1][np2][next] = max(dp[nbit][np1][np2][next],
					       np3);
	      }
	    }
	  }
	}
      }
      int maxi = 0;
      rep(j,MAX) rep(k,MAX) if( dp[(1<<3)-1][j][k][n&1] != -1 ) {
	maxi = max(maxi,dp[(1<<3)-1][j][k][n&1]+j+k);
      }
      return maxi;
    }
  };