状态压缩dp
详见代码
/*
状态压缩dp
dp[ i ][ j ]:第i行j状态的最大和
dp[i][j] = max( dp[i-1][k]+sum[i][j] );
题意：给定一个N*N的方格，让你在里面取出一些数使其和最大，要求每一个数不能与其相邻的8个数同时取出
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
using namespace std;
const int maxn = ;
int sum[ maxn+ ][ <<maxn ];//sum[i][j]：第i行j状态的数字和
int s[ <<maxn ];//合格的状态的集合
int dp[ maxn+ ][ <<maxn ];//dp[i][j]:第i行j状态的最大和
int mat[ maxn+ ][ maxn+ ];
int binary[ maxn+ ];
void init_binary( ){
binary[ ] = ;
for( int i=;i<;i++ ){
binary[ i ] = *binary[ i- ];
}
} int solve( int n ){
int cnt_state = ;
memset( dp,,sizeof( dp ) );
memset( sum,,sizeof( sum ) );
int N = (<<n);
for( int i=;i<N;i++ ){
if( ((i<<)&i)== ){
s[ cnt_state++ ] = i;
}
}//选出无相邻数字的状态
for( int i=;i<n;i++ ){
for( int j=;j<cnt_state;j++ ){
for( int k=;k<n;k++ ){
if( binary[k]&s[ j ] ){
sum[ i ][ j ] += mat[ i ][ k ];
}
}
}
}//预处理出sum值
int ans = ;
for( int i=;i<cnt_state;i++ ){
dp[][ i ] = sum[ ][ i ];
ans = max( ans,dp[][i] );
}
for( int i=;i<n;i++ ){
for( int j=;j<cnt_state;j++ ){
for( int k=;k<cnt_state;k++ ){//前一行的状态
if( (s[j]&s[k])== ){
if( (s[j]&(s[k]<<))== ){
if( (s[j]&(s[k]>>))== ){
dp[ i ][ j ] = max( dp[ i- ][ k ]+sum[ i ][ j ],dp[ i ][ j ] );
}
}
}
}
ans = max( ans,dp[i][j] );
}
}
return ans;
} int main(){
char str[ ];
init_binary();
while( gets( str ) ){
int len = strlen( str );
int n = ;
for( int i=;i<len;i+= ){
mat[][n++] = (str[i]-'')*+str[i+]-'';
}
for( int i=;i<n;i++ ){
gets(str);
int cc = ;
for( int j=;j<len;j+= ){
mat[i][cc++] = (str[j]-'')*+str[j+]-'';
}
}
int ans = solve( n );
printf("%d\n",ans);
getchar();
}
return ;
}