oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

SRM388

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

Feedback

# re: SRM388   回复  更多评论   

2008-01-17 22:23 by wywcgs
那个“表面上貌似这一行被引用了2^n*2^k次”,实际上确实是这么多次吧,枚举一下k,能发现和就是3^n

# re: SRM388   回复  更多评论   

2008-01-17 23:08 by oyjpart
恩,我的意思是表面上看起来是2^n*2^k次而不知最终的复杂度,最好是通过均摊分析的思想来得知是3^n的复杂度。呵呵~~ :) 加油考研哦~

# re: SRM388   回复  更多评论   

2008-01-21 23:45 by wywcgs
最好的方法就是生算,把这个式子从k = 0到n加起来求和,然后会发现就是3^n.....

考完才看到你的祝福,thx :)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理