zoj3471 状态压缩dp基础

/*
dp[S]表示状态S下的最大收益，0表示没有了，1表示还在 
*/
#include<bits/stdc++.h>
using namespace std;
int dp[1<<11],mp[11][11],n;
int main(){
    while(cin>>n && n){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)cin>>mp[i][j];
        memset(dp,0,sizeof dp);
        int ans=0;
        
        for(int S=(1<<n)-1;S>=1;S--)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)//消去i留下j 
                    if( (S&(1<<(i-1))) && (S&(1<<(j-1))) && i!=j )
                        dp[S-(1<<(i-1))]=max(dp[S-(1<<(i-1))],dp[S]+mp[j][i]),ans=max(ans,dp[S-(1<<(i-1))]); 
        printf("%d
",ans);            
    }
}