AOJ 1619 Making Lunch Boxes

#include<bits/stdc++.h>
using namespace std;

int dp[2][(1<<24)];
string s[501];
int n,m;
bool a[501][501];

int main(){
  while(cin>>n>>m,n){
    for(int i=0;i<n;i++){
      cin>>s[i];
      for(int j=0;j<m;j++){
        a[i][j]=(s[i][j]=='1');
      }
    }
    if(n<=m){
      int ans=0;
      for(int i=0;i<(1<<n);i++){
        if(ans>=__builtin_popcount(i))continue;
        bool ok=1;
        for(int j=0;j<m;j++){
          int cont=0;
          for(int k=0;k<n;k++){
            if(a[k][j] && i&(1<<k))cont++;
          }
          if(cont&1){ok=0;break;}
        }
        if(ok)ans=max(ans,__builtin_popcount(i));
      }
      cout<<ans<<endl;
    }else{
      int list[501];
      fill(list,list+n,0);
      for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          if(a[i][j]){
            list[i]=list[i]|(1<<j);
          }
        }
      }
      for(int i=0;i<2;i++)for(int j=0;j<(1<<m);j++)dp[i][j]=-1;
      dp[0][0]=0;
      for(int i=0;i<n;i++){
        for(int j=0;j<(1<<m);j++)dp[(i+1)&1][j]=-1;
        for(int j=0;j<(1<<m);j++){
          if(dp[i&1][j]==-1)continue;
          dp[(i+1)&1][j^list[i]]=max(dp[(i+1)&1][j^list[i]],dp[i&1][j]+1);
          dp[(i+1)&1][j]=max(dp[(i+1)&1][j],dp[i&1][j]);
        }
      }
      cout<<dp[n&1][0]<<endl;
    }
  }
}

• 基本的には審判長講評に書いてあることをそのまま実装.
• n<=mなら「どのメニューを作るか」の組合せで全探索.
• n>mならbitDP.
• 漸化式はdp[(今、選ぶかどうか考えているメニューの番号:i)%2][1つ余っている素材の集合を表すbit列:j]:=この状況になるようなメニューの組合せのうち最大のメニュー数
• よって、dp[(i+1)%2][j^list[i]]=max(dp[(i+1)%2][j^list[i]],dp[i%2][j])
• もうひとつは、dp[(i+1)%2][j]=max(dp[(i+1)%2][j],dp[i%2][j])
• ここで、list[i]はi番目のメニューで使われる素材の集合を表すbit列です.
• 最後はひとつも素材を余らせてはいけないのでdp[n%2][0]を出力します.
• のりで配列の再利用をしたけど、しなくてもいけるのかな?
• あ、あと__builtin_popcount(i)はiを二進数で表した時に1になっている桁の個数です.
• 例)__builtin_popcount(7)=3,__builtin_popcount(8)=1,__builtin_popcount(9)=2
• 初期化をミスして2時間無駄にしたのはココだけの話.