简单的压缩状态
dp
1 /* 2 状态压缩dp 3 同hdu2167 4 利用滚动数组！！ 5 */ 6 #include<stdio.h> 7 #include<string.h> 8 #include<stdlib.h> 9 #include<algorithm> 10 #include<iostream> 11 #include<queue> 12 #include<stack> 13 #include<math.h> 14 #include<map> 15 using namespace std; 16 const int maxn = 20; 17 int binary[ maxn+5 ]; 18 int s[ 1<<(maxn) ]; 19 //int sum[ maxn ][ 1<<maxn ]; 20 //int dp[ maxn ][ 1<<maxn ]; 21 int dp[2][1<<maxn]; 22 int mat[ maxn ][ maxn ]; 23 void init_binary(){ 24 binary[0] = 1; 25 for( int i=1;i<=20;i++ ){ 26 binary[i] = 2*binary[i-1]; 27 } 28 } 29 30 int solve( int n ){ 31 //memset( sum,0,sizeof( sum ) ); 32 memset( dp,0,sizeof( dp ) ); 33 int cnt = 0; 34 int N = (1<<n); 35 for( int i=0;i<N;i++ ){ 36 if( ( (i<<1)&i )==0 ){ 37 s[ cnt++ ] = i; 38 } 39 }//保存合格的状态 40 //for( int i=0;i<n;i++ ){ 41 //for( int j=0;j<cnt;j++ ){ 42 //for( int k=0;k<n;k++ ){ 43 //if( binary[k]&s[j] ){ 44 //sum[ i ][ j ] += mat[ i ][ k ]; 45 //} 46 //} 47 //} 48 //} 49 int ans = 0; 50 for( int i=0;i<cnt;i++ ){ 51 int sum = 0; 52 for( int j=0;j<n;j++ ){ 53 if( binary[j]&s[i] ){ 54 sum += mat[0][j]; 55 } 56 } 57 dp[0][i] = sum; 58 ans = max( ans,dp[0][i] ); 59 } 60 for( int i=1;i<n;i++ ){ 61 for( int j=0;j<cnt;j++ ){ 62 for( int k=0;k<cnt;k++ ){ 63 if( ( s[j]&s[k] )==0 ){ 64 int sum = 0; 65 for( int kk=0;kk<n;kk++ ){ 66 if( binary[kk]&s[j] ){ 67 sum += mat[i][kk]; 68 } 69 } 70 if( i%2==1 ) dp[ 1 ][ j ] = max( dp[1][j],dp[0][k]+sum ); 71 else dp[ 0 ][ j ] = max( dp[0][j],dp[1][k]+sum ); 72 //dp[ i ][ j ] = max( dp[i][j],dp[i-1][k]+sum ); 73 //dp[i][j] = max( dp[i][j],dp[i-1][k]+sum[i][j] ); 74 } 75 } 76 ans = max( ans,max( dp[1][j],dp[0][j] ) ); 77 } 78 } 79 return ans; 80 } 81 82 int main(){ 83 int n; 84 init_binary(); 85 while( scanf("%d",&n)==1 ){ 86 for( int i=0;i<n;i++ ){ 87 for( int j=0;j<n;j++ ){ 88 scanf("%d",&mat[i][j]); 89 } 90 } 91 int ans = solve( n ); 92 printf("%d ",ans); 93 } 94 return 0; 95 }