题目大意就是给你一个矩阵，矩阵每个格子都有数，然后你可以选一些格子，获得一些值，然后要你求可以获得的最大值是多少，还有选取的格子不能相邻。废话不多说了直接看代码把
这种用一个数来表示一组数，以降低表示状态所需的维数的解题手段，就叫做状态压缩。
#include<bits/stdc++.h>
using namespace std;
int dp[20][7000],sta[7000],mp[20][20];//dp[i][j]表示前i行，第i行取第j状态所能取得的最大值
int n,moststa;
bool ok(int x)
{
if(!(x&(x<<1)))
return true;
return false;
}
void findsta()//求出单行的所有合法情况，即相邻的位子不取
{
memset(sta,0,sizeof(sta));
moststa=0;
int last=(1<<n)-1;
for(int i=0;i<=last;i++)
if(ok(i))
sta[++moststa]=i;
// cout<<"MOSTSTA:"<<moststa<<endl;
//for(int i=1;i<=moststa;i++)
// cout<<sta[i]<<" ";
// cout<<endl<<endl;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&(mp[i][j]));
memset(dp,0,sizeof(dp));
findsta();
for(int i=1;i<=moststa;i++)
{
for(int j=n-1;j>=0;j--)
if((sta[i]>>j)&1)//满足说明第n-1-j列的状态为1
{
dp[0][i]+=mp[0][n-1-j];
}
}
//for(int i=1;i<=moststa;i++)
// cout<<dp[0][i]<<" ";
// cout<<endl<<endl;
for(int i=1;i<n;i++)
for(int k=1;k<=moststa;k++)//枚举第i行状态，求解dp[i][1~moststa]
{
for(int j=1;j<=moststa;j++)//枚举i-1行状态，由i-1行的状态转移至i行的状态
{
if((sta[j]&sta[k])!=0||((sta[j]>>1)&sta[k])!=0||((sta[j]<<1)&sta[k])!=0)//状态冲突换下一个状态
continue;
int tmp=0;
for(int mmp=n-1;mmp>=0;mmp--)//求由该状态可以获取到的值
if((sta[k]>>mmp)&1)
{
tmp+=mp[i][n-1-mmp];
}
dp[i][k]=max(dp[i][k],tmp+dp[i-1][j]);
}
}
//for(int i=1;i<=moststa;i++)
// cout<<dp[1][i]<<" ";
//cout<<endl<<endl;
int maxx=-1;
for(int k=1;k<=moststa;k++)
maxx=max(maxx,dp[n-1][k]);
cout<<maxx<<endl;
}
return 0;
}
时隔一年再写了一遍
#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs (rt<<1)+1
#define PI acos(-1)
#define eps 1e-8
#define ll long long
#define fuck(x) cout<<#x<<" "<<x<<endl;
typedef pair<int,int> pii;
const int inf=2e9;
const int maxn=1e6+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
//int lowbit(int x){return x&-x;}
//void add(int x,int v){while(x<=n)bit[x]+=v,x+=lowbit(x);}
//int sum(int x){int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
inline ll read() {
ll s = 0,w = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') w = -1;
ch = getchar();
}
while(isdigit(ch))
s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
inline void write(ll x) {
if(x < 0)
putchar('-'), x = -x;
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
int n,mp[10][20],state[64000],val[20][64000],dp[20][64000],tot;
void cal(int sta){
for(int i=1;i<=n;i++)
{
for(int j=n-1;j>=0;j--)
val[i][tot]+=mp[i][n-j]*((sta>>j)&1);
}
}
void init(){
for(int i=0;i<(1<<n);i++){
if(!(i&(i<<1))){
state[++tot]=i;
cal(i);
}
}
}
int main(){
int t,ans;
t=read();
while(t--){
memset(val,0,sizeof(val));
memset(dp,0,sizeof(dp));
ans=tot=0;
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=read();
init();
for(int i=1;i<=tot;i++){
dp[1][i]=val[1][i];
}
for(int i=2;i<=n;i++){
for(int j=1;j<=tot;j++) {
for (int k = 1; k <= tot; k++) {
if ((state[j] & state[k] )|| ((state[j] << 1) & state[k]) || ((state[j] >> 1) & state[k]))
continue;
dp[i][j] = max(dp[i - 1][k] + val[i][j], dp[i][j]);
}
}
}
for(int j=1;j<=tot;j++) ans=max(ans,dp[n][j]);
write(ans);puts("");
}
return 0;
}