> 速度快的都是搜索的优化出来的吧。二楼说的DP不知道怎么搞？
其实也就是个记忆化搜索..
首先,如果某列中第i行和第j行都为1,那么不能把i和j行都选中了,称i行与j行矛盾.
那么,可以预处理出和每行矛盾的行,打包到一个int中,第j位是1表示i行与j行矛盾
同时预处理每行的和
设f[s]表示还有状态为s(可用行)时最大的和.
求出 f[111..11],如果等于列数的话就有解.

void dodp(int u)
{
	if(done[u])
		return;
	done[u]=1;
	for(int i=0;i<n;i++)
		if(((1<<i)&u))
		{
			dodp((u|fbd[i])-fbd[i]);
			dp[u]=max(dp[u],sum[i]+dp[(u|fbd[i])-fbd[i]]);
		}
}

• Re:请问几十秒的大牛是用什么方法做的？我只会暴搜，250ms。。。 (76) MasterLuo 2009-08-23 18:06:51
  • dp vector + bitset (84) HowLongTheIDCanBe 2009-08-23 19:20:45
• Re:好！ (404) Headacher 2009-08-23 20:52:35