Posted on 2008-01-16 03:09
oyjpart 閱讀(1251)
評論(3) 編輯 收藏 引用 所屬分類:
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) 的