hdu 5823 color II —— 子集DP
题目：http://acm.hdu.edu.cn/showproblem.php?pid=5823
看博客：http://www.cnblogs.com/SilverNebula/p/5929550.html
学到了求子集中独立集的姿势~
还有那个子集DP真是太妙了！
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int T,n,mp[20],f[1<<20],S,inf=0x3f3f3f3f; bool inv[1<<20]; ll ans,mod=(1ll<<32); int main() { scanf("%d",&T); while(T--) { memset(mp,0,sizeof mp); memset(f,0,sizeof f); memset(inv,0,sizeof inv); scanf("%d",&n); S=(1<<n)-1; for(int i=0;i<n;i++) for(int j=0,x;j<n;j++) { scanf("%1d",&x); if(x)mp[i]|=(1<<j); } for(int s=1;s<=S;s++) { bool fl=0; for(int i=0;i<n;i++) if((s&(1<<i))&&(s&mp[i])){fl=1; break;} if(!fl)inv[s]=1; } for(int s=1;s<=S;s++) { int tmp=inf; for(int i=s;i;i=(i-1)&s) if(inv[i])tmp=min(tmp,f[s^i]+1); f[s]=tmp; } ll tmp=1; ans=0; for(int i=1;i<=S;i++) { tmp=(tmp*233)%mod; ans=(ans+f[i]*tmp)%mod; } printf("%lld ",ans); } return 0; }