oyjpArt ACM/ICPC算法程序設計空間

第一題，純暴搞的題，應當要寫的更快些。
第二題。DP。題目稍些復雜。不用說了，我這等菜鳥，又是掛掉了。。sigh...

依靠一個cha，顏色變黃。

corret solution :

const int N = 15;
int dp[two(N)];
int adj[N];
int n;

int go(int x) {

 int i, k, j;
 int &ret = dp[x];

 if(ret != -1) return ret;
 
 int all = 0;
 for(i = 0; i < n; ++i) {
  if(contains(x, i)) {
   all |= adj[i];
  }
 }
 if(all != two(n)-1) return ret = 0;

 ret = 1;

 int b[N];
 for(i = 0, k = 0; i < n; ++i) if(contains(x, i)) b[k++] = i;

 for(i = 0; i < two(k)-1; ++i) {
  int y = 0, z = 0;
  for(j = 0; j < k; ++j) {
   if(contains(i, j)) y |= two(b[j]);
   else z |= two(b[j]);
  }
  ret = Max(ret, go(y) + go(z));         // 注意 表面上貌似這一行被引用了2^n*2^k次，但實際上只有3^n (利用均攤分析的思想，相當于分成了3個集合)
 }
 return ret;
}

class InformFriends
{
public:
 int maximumGroups(vector <string> f)
 {
  n = sz(f);
  memset(adj, 0, sizeof(adj));
  int i, j;
  for(i = 0; i < n; ++i) {
   adj[i] |= two(i);
   for(j = 0; j < n; ++j) {
    if(f[i][j] == 'Y')
     adj[i] |= two(j);
   }
  }

  memset(dp, -1, sizeof(dp));
  return go(two(n)-1);
 } 

 賽后看到其他很多人的代碼，很有趣，各種各樣的都有
比如通過 for(i = 0; i < (1<<n); (i+mask+1)&~mask) 來尋找mask補集的子集
也有 for(i = ~mask&(1<<n); i > 0; i = (i-1)&mask) 的