Marriage Ceremonies LightOJ - 1011
常规状压dp。popcount(S)表示S集合中元素数量。ans[S]表示S中的女性与前popcount(S)个男性结婚的最大收益。
那么，$ans[S]=max\{ans[S-p]+a[popcount(S)][p]\}$
老代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int ans[17][70000],a[17][17],T,TT,n; 6 int main() 7 { 8 int i,j,k; 9 scanf("%d",&T); 10 for(TT=1;TT<=T;TT++) 11 { 12 scanf("%d",&n); 13 for(i=1;i<=n;i++) 14 for(j=1;j<=n;j++) 15 scanf("%d",&a[i][j]); 16 memset(ans,0,sizeof(ans)); 17 for(i=1;i<=n;i++) 18 for(j=0;j<(1<<n);j++) 19 { 20 if(__builtin_popcount(j)!=i) continue; 21 for(k=1;k<=n;k++) 22 if(j&(1<<(k-1))) 23 ans[i][j]=max(ans[i][j],ans[i-1][j^(1<<(k-1))]+a[i][k]); 24 } 25 printf("Case %d: %d\n",TT,ans[n][(1<<n)-1]); 26 } 27 return 0; 28 }
新代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int ans[70000],a[17][17],T,TT,n; 6 int main() 7 { 8 int i,j,k; 9 scanf("%d",&T); 10 for(TT=1;TT<=T;TT++) 11 { 12 scanf("%d",&n); 13 for(i=1;i<=n;i++) 14 for(j=1;j<=n;j++) 15 scanf("%d",&a[i][j]); 16 memset(ans,0,sizeof(ans)); 17 for(i=1;i<(1<<n);i++) 18 for(j=1;j<=n;j++) 19 if(i&(1<<(j-1))) 20 ans[i]=max(ans[i],ans[i^(1<<(j-1))]+a[__builtin_popcount(i)][j]); 21 printf("Case %d: %d\n",TT,ans[(1<<n)-1]); 22 } 23 }
Marriage Ceremonies LightOJ - 1011
原文：http://www.cnblogs.com/hehe54321/p/loj-1011.html