most powerful ZOJ3471

本文主要是介绍most powerful ZOJ3471，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用0表示存在原子，1表示原子已经被撞掉了。。。 dp[j]表示状态为j的时候的most powerful，对于j的二进制，寻找两个不同的0，状态转移。

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int a[11][11],dp[1025],s[12]={0,1,2,4,8,16,32,64,128,256,512,1024};
int main()
{int i,j,n,l,r,ans;for(s[1]=1,i=2;i<=11;i++) s[i]=s[i-1]<<1;while(scanf("%d",&n)!=EOF&&n){for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&a[i][j]);memset(dp,0,sizeof(dp));for(j=0;j<s[n+1];j++){for(l=1;l<n;l++)if((j&s[l])==0)for(r=l+1;r<=n;r++)if((j&s[r])==0){dp[j|s[l]]=max(dp[j|s[l]],dp[j]+a[r][l]);dp[j|s[r]]=max(dp[j|s[r]],dp[j]+a[l][r]);}}for(i=s[n+1]-1,ans=0,j=1;j<=n;j++) ans=max(ans,dp[i-s[j]]);printf("%d\n",ans);}
}

这篇关于most powerful ZOJ3471的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---