题解和取数方格

题目

题目描述 Problem Description

给定一个n乘n的网格棋盘，每个单元格中包含一个非负数值。现需从中选取若干数值，要求所选数值对应的单元格之间不得存在共享边的情况，即任意两个被选中的单元格不能相邻，同时确保所选取数值的总和达到最大值。

输入处理与数据获取

该测试案例集合由多个实例组成，每个实例包含一个整数n以及n\times n个非负数值，且满足n\leq 20的条件。

输出 Output

针对每一个测试样本，所能获得的最高输出值为

样例输入 Sample Input

    3
    75 15 21 
    75 15 28 
    34 70 5 
    
    
      
      
      
      
    

样例输出 Sample Output

    188
    
    
      
    

题解

思路

我们可以采用自上而下的方式，逐行挑选对应的格子。在进行某一行的格子选择时，其决策仅依赖于前一行的选择方案，因此可以将“当前所处的行数以及当前行的选择状态”作为动态规划的状态参数。

在此过程中，我们需要运用状态压缩这一技术：每一行中被选中的格子实际