题解 P1123 【取数游戏】

神一般的世界 · 2016-10-26 18:53:36 · 题解

状压DP最好了（难得一时兴起来一波牛刀杀鸡）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=10,M=256;
int a[N][N],f[N][M],num[M],jump[N];
int T,n,m,ans,tot=0;
int main(){
    for(int i=0;i<(1<<7);i++)if(!(i&(i<<1))){tot++;num[tot]=i;}//先求出好的状态
    jump[0]=1;jump[1]=2;for(int i=2;i<N;i++)jump[i]=jump[i-1]+jump[i-2];//推出每种m对应的好的状态数
    scanf("%d",&T);
    for(int ii=1;ii<=T;ii++){
        memset(f,0,sizeof(f));ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=jump[m];j++){
                int t=num[j];int sum=0;
                for(int l=m;l>=1;l--,t=t>>1)if(t&1)sum+=a[i][l];
                for(int k=1;k<=jump[m];k++){
                    if((num[j]&num[k])||(num[j]&(num[k]<<1))||(num[j]&(num[k]>>1)))continue;
                    else f[i][j]=max(f[i][j],sum+f[i-1][k]);
                }
            }
        }
        for(int i=1;i<=jump[m];i++)ans=max(ans,f[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}