Posted on 2008-01-16 03:09
oyjpart 阅读(1248)
评论(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) 的