状态压缩dp
详见代码
1 /* 2 状态压缩dp 3 dp[ i ][ j ]:第i行j状态的最大和 4 dp[i][j] = max( dp[i-1][k]+sum[i][j] ); 5 题意：给定一个N*N的方格，让你在里面取出一些数使其和最大，要求每一个数不能与其相邻的8个数同时取出 6 */ 7 #include<stdio.h> 8 #include<string.h> 9 #include<stdlib.h> 10 #include<algorithm> 11 #include<iostream> 12 #include<queue> 13 #include<stack> 14 #include<math.h> 15 #include<map> 16 using namespace std; 17 const int maxn = 15; 18 int sum[ maxn+5 ][ 1<<maxn ];//sum[i][j]：第i行j状态的数字和 19 int s[ 1<<maxn ];//合格的状态的集合 20 int dp[ maxn+5 ][ 1<<maxn ];//dp[i][j]:第i行j状态的最大和 21 int mat[ maxn+5 ][ maxn+5 ]; 22 int binary[ maxn+5 ]; 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 int cnt_state = 0; 32 memset( dp,0,sizeof( dp ) ); 33 memset( sum,0,sizeof( sum ) ); 34 int N = (1<<n); 35 for( int i=0;i<N;i++ ){ 36 if( ((i<<1)&i)==0 ){ 37 s[ cnt_state++ ] = i; 38 } 39 }//选出无相邻数字的状态 40 for( int i=0;i<n;i++ ){ 41 for( int j=0;j<cnt_state;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 }//预处理出sum值 49 int ans = 0; 50 for( int i=0;i<cnt_state;i++ ){ 51 dp[0][ i ] = sum[ 0 ][ i ]; 52 ans = max( ans,dp[0][i] ); 53 } 54 for( int i=1;i<n;i++ ){ 55 for( int j=0;j<cnt_state;j++ ){ 56 for( int k=0;k<cnt_state;k++ ){//前一行的状态 57 if( (s[j]&s[k])==0 ){ 58 if( (s[j]&(s[k]<<1))==0 ){ 59 if( (s[j]&(s[k]>>1))==0 ){ 60 dp[ i ][ j ] = max( dp[ i-1 ][ k ]+sum[ i ][ j ],dp[ i ][ j ] ); 61 } 62 } 63 } 64 } 65 ans = max( ans,dp[i][j] ); 66 } 67 } 68 return ans; 69 } 70 71 int main(){ 72 char str[ 105 ]; 73 init_binary(); 74 while( gets( str ) ){ 75 int len = strlen( str ); 76 int n = 0; 77 for( int i=0;i<len;i+=3 ){ 78 mat[0][n++] = (str[i]-'0')*10+str[i+1]-'0'; 79 } 80 for( int i=1;i<n;i++ ){ 81 gets(str); 82 int cc = 0; 83 for( int j=0;j<len;j+=3 ){ 84 mat[i][cc++] = (str[j]-'0')*10+str[j+1]-'0'; 85 } 86 } 87 int ans = solve( n ); 88 printf("%d ",ans); 89 getchar(); 90 } 91 return 0; 92 }