不再孤独的HandsomeHow 状压dp

本文主要是介绍不再孤独的HandsomeHow 状压dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

G. 不再孤独的HandsomeHow

Sample Input

220 22 040 2 4 62 0 8 34 8 0 76 3 7 0

Sample Output

214

Hint

#include<cstdio>
#include<cstring>
#define MAX(x,y) ((x)>(y)?(x):(y))
int v[16][16];
int n;
int dp[1<<15];
void show(int x)
{for(int i=0;i<n;i++){if(x>>i&1)printf("1");elseprintf("0");}printf("\n");
} 
int dfs(int s)
{
//	printf("begin dp=%d   ",dp[s]);
//	show(s);if(dp[s]>=0)return dp[s];if(s==(1<<n)-1)return dp[s]=0;int res=-1;for(int p=0;p<n;p++){if(!(s>>p&1)){for(int k=0;k<n;k++){if(k!=p&&!(s>>k&1)){//				printf("p=%d k=%d   v=%d  \n",p,k,v[p][k]); res=MAX(res,dfs(s|1<<p|1<<k)+v[p][k]);
//					printf("res=%d\n"); }}}}
///	printf("end dp=%d  ",dp[s]);
//	show(s);return dp[s]=res;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);memset(dp,-1,sizeof(dp));for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&v[i][j]);printf("%d\n",dfs(0));}
}

这篇关于不再孤独的HandsomeHow 状压dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---