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];
		}
};