题解 | 取数游戏

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { 
            int t=in.nextInt();
            in.nextLine();
            while(t>0){
                t--;
                int n = in.nextInt();
                int m = in.nextInt();
                in.nextLine();
                int[][] board=new int[n][m];
                for(int i=0;i<n;i++){
                    board[i]=Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                }
                //列举单层所有可能的情况，用二进制存储实际取出状态，1表示取出0表示舍弃
                List<Integer> valid=new ArrayList<>();
                for(int i=0;i<(1<<m);i++){
                    if(((i>>1)&i)==0){//右移一位后与运算，检查是否存在相邻的情况
                        valid.add(i);
                    }
                }
                int len=valid.size();
                //遍历原数组每一行，通过比对valid计算每一种情况的单层和
                int[][] rowSum=new int[n][len];
                for(int i=0;i<n;i++){
                    for(int j=0;j<len;j++){
                        int mask=valid.get(j);//第j种取出方式
                        int sum=0;
                        //遍历该种情况下的取出数进行sum
                        for(int k=0;k<m;k++){
                            if(((mask>>k)&1)==1)sum+=board[i][k];
                        }
                        rowSum[i][j]=sum;
                    }
                }
                //计算相邻两行选择是否冲突
                boolean[][] compatible=new boolean[len][len];
                for(int i=0;i<len;i++){
                    int mask1=valid.get(i);
                    for(int j=0;j<len;j++){
                        int mask2=valid.get(j);
                        if((mask1&mask2)>0)continue;//直接上下相邻
                        if((((mask1>>1)&mask2)>0))continue;//在上一行的右下,对应着上一行是当前行的左上
                        if((((mask1<<1)&mask2)>0))continue;//在上一行的左下
                        compatible[i][j]=true;
                    }
                }
                //动态规划多行的结果
                int[][] dp=new int[n][len];
                    //初始化第一行
                for(int i=0;i<len;i++){
                    dp[0][i]=rowSum[0][i];
                }
                    //当前计算的行，初始标记为不可达状态
                for(int i=1;i<n;i++){
                    Arrays.fill(dp[i],Integer.MIN_VALUE);
                    for(int j=0;j<len;j++){//第i行的取用方式
                        for(int k=0;k<len;k++){//上一行的取用方式
                            //只有上一行和当前行的取用方式不冲突时才有效
                            if(compatible[j][k]){
                                //dp结果就是上一行结果加上当前行的sum
                                dp[i][j]=Math.max(dp[i][j],dp[i-1][k]+rowSum[i][j]);
                            }
                        }
                    }
                }
                int res=0;
                for(int i:dp[n-1]){
                    res=Math.max(res,i);
                }
                System.out.println(res);
            }

        }
    }
    
}