题意：给你一个n*n的矩阵，让你从矩阵中选择一些数是的他们的和最大，规则是：相邻的两个数不能同时取，位置为（i,j）的数与(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1)相邻。
思路：很常见的状态压缩dp，设dp[i][j]表示前i行，第i行状态为j时的最大和，那么dp[i][j] = max(dp[i-1][k]) + (该状态下取第i行的那些数的和)。
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 16;
const int MAXM = 1700;
int status[MAXM],cnt;
int dp[MAXN][MAXM],mat[MAXN][MAXN];
void createStatus(int n){
cnt = 0;
int up = (1 << n);
for(int i = 0;i < up;i ++){
if(i & (i << 1)) continue;
status[cnt++] = i;
}
}
int calSum(int n,int m){
int ret = 0;
for(int i = 0;i < 16;i ++)
if(m & (1 << i)) ret += mat[n][i];
return ret;
}
void init(int n){
createStatus(n);
memset(dp,0,sizeof dp);
for(int i = 0;i < cnt;i ++) dp[0][i] = calSum(0,status[i]);
}
bool isValid(int n,int m){
if(n & m) return false;
if((n << 1) & m || (m << 1) & n) return false;
return true;
}
void work(int n){
init(n);
for(int i = 1;i < n;i ++){
for(int j = 0;j < cnt;j ++){
for(int k = 0;k < cnt;k ++){
if(!isValid(status[j],status[k])) continue;
dp[i][j] = max(dp[i-1][k],dp[i][j]);
}
dp[i][j] += calSum(i,status[j]);
}
}
int ans = 0;
for(int i = 0;i < cnt;i ++) ans = max(ans,dp[n-1][i]);
printf("%d
",ans);
}
int main(){
char str[MAXN*4];
//freopen("in.cpp","r",stdin);
while(gets(str)){
int n(0),len(strlen(str));
for(int i = 0;i < len;i += 3){
mat[0][n++] = (str[i]-'0')*10 + str[i+1] - '0';
}
for(int i = 1;i < n;i ++){
for(int j = 0;j < n;j ++) scanf("%d",&mat[i][j]);
}
work(n);
getchar(),getchar();
}
return 0;
}