TopCoder SRM 388 Div1 Medium InformFriends

問題

N人の友達がいる。
N人のそれぞれが互いに友達であるかはfriends[]により与えられる。

友達に噂を出来るだけ多くの個数だけ伝えたい。
一人の友達につき、伝えられる噂の数は1つだけである。
噂を聞いた友達は、自分の友達にだけその噂を伝える（その友達の友達には伝わらない）。

このとき、全員が共有できる噂の数の最大値を求めよ。

制約条件

N≦15

方針

友達から「同じ噂を伝える人の集合」を一つ決める。
すると、その集合に対して一つの噂を伝えたときに、全員に伝わるかそうでないかがわかる。

dp[mask]を、そのmask集合の人に噂を伝え終えた後での、全員に伝わった噂の数の最大値とすると、
全員に伝わるような友達の選び方iについて、
dp[mask]=max(dp[mask^i]+1)が成り立つ。
なので、部分集合に対して更新していくようなDPをすれば答えがO(3^n)で求まる。

ソースコード

bool ok[1<<15];
int dp[1<<15];

class InformFriends {
  public:
  int maximumGroups(vector <string> friends) {
    int n=friends.size();
    rep(i,1<<n){
      int mask=i;
      rep(j,n)rep(k,n)
        if((i&1<<j)&&friends[j][k]=='Y')mask|=1<<k;
      ok[i]=mask==(1<<n)-1;
    }
    memset(dp,0,sizeof(dp));
    rep(i,1<<n)for(int j=i;j;j=(j-1)&i)
      dp[i]=max(dp[i],dp[i^j]+ok[j]);
    return dp[(1<<n)-1];
  }
};