首页 > 代码库 > zoj3471Most Powerful 状压dp

zoj3471Most Powerful 状压dp

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int n;int Map[11][11];int dp[1<<11];int Max(int a,int b){    return a>b?a:b;}int gao(int x){    if(x==0) return dp[x]=0;    if(~dp[x]) return dp[x];    int ret= 0;    for(int i=0;i<n;i++)    if(x&(1<<i)){        for(int j=0;j<n;j++){            if(x&(1<<j)){                if(i==j) continue;// 这个一定要加 ,自己不能把自己给搞了                ret=Max(ret,gao(x^(1<<j))+Map[i][j]);            }        }    }    return dp[x]= ret;}int  main(){    while(cin>>n,n){        memset(dp,-1,sizeof(dp));        memset(Map,0,sizeof(Map));        for(int i=0;i<n;i++)            for(int j=0;j<n;j++)            scanf("%d",&Map[i][j]);        int gg=(1<<n) -1 ;        cout<<gao(gg)<<endl;    }    return 0;}