SRM388div1 medium
分からなかった。
ビットを使って部分集合を求めると結構速いらしい。
このDPの計算量はそれぞれのビットについて
(mask:0,sub:0),(mask:1,sub:0),(mask:1,sub:1)
の場合があるので3^nなんだって。
2^n*2^nしか思いつかなかった。
#include <vector> using namespace std; int OK[1<<15]; int DP[1<<15]; class InformFriends { public: int maximumGroups(vector<string> _friends) { int n; vector<int> friends; n=_friends.size(); for(int i=0;i<n;i++) { int a=(1<<i); for(int j=0;j<n;j++) if(_friends[i][j]=='Y') a+=(1<<j); friends.push_back(a); } for(int i=0;i<(1<<n);i++) { int a=0; for(int j=0;j<n;j++) if(i&(1<<j)) a|=friends[j]; OK[i]=(a==(1<<n)-1); } for(int mask=0;mask<(1<<n);mask++) { DP[mask]=0; int m=mask; while(m!=0) { if(OK[m]) DP[mask]=max(DP[mask],DP[mask^m]+1); m--; m&=mask; } } return DP[(1<<n)-1]; } };