帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 � × � n×m 的矩阵，矩阵中的每个元素 � � , � a i,j ​ 均为非负整数。游戏规则如下： 每次取数时须从每行各取走一个元素，共 � n 个。经过 � m 次后取完矩阵内所有元素； 每次取走的各个元素只能是该元素所在行的行首或行尾； 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 × 2 � ×2 i ，其中 � i 表示第 � i 次取数（从 1 1 开始编号）； 游戏结束总得分为 � m 次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 输入格式 输入文件包括 � + 1 n+1 行： 第一行为两个用空格隔开的整数 � n 和 � m。 第 2 ∼ � + 1 2∼n+1 行为 � × � n×m 矩阵，其中每行有 � m 个用单个空格隔开的非负整数。 输出格式 输出文件仅包含 1 1 行，为一个整数，即输入矩阵取数后的最大得分。 输入输出样例 输入 #1复制 2 3 1 2 3 3 4 2 输出 #1复制 82 说明/提示 【数据范围】 对于 60 % 60% 的数据，满足 1 ≤ � , � ≤ 30 1≤n,m≤30，答案不超过 1 0 16 10 16 。 对于 100 % 100% 的数据，满足 1 ≤ � , � ≤ 80 1≤n,m≤80， 0 ≤ � � , � ≤ 1000 0≤a i,j ​ ≤1000。 【题目来源】 NOIP 2007 提高第三题。 在洛谷， 享受 Coding 的欢乐

这是一道经典的动态规划问题，可以使用记忆化搜索或者自底向上的动态规划方法来解决。

记忆化搜索：

用一个三维数组 $dp[i][j][k]$ 表示当前已经取了前 $i$ 行，第 $j$ 行取的是行首还是行尾，第 $k$ 次取数时的最大得分。

递归式为：

$$dp[i][j][k] = \max\limits_{p=0}^{1}\{dp[i-1][p][k-1]+a_{i,j}\times2^k\}$$

其中 $p$ 表示上一行取的是行首还是行尾，$a_{i,j}$ 表示矩阵中第 $i$ 行第 $j$ 列的数字。

边界条件为：

$$dp[0][0][0] = 0$$

$$dp[1][0][1] = a_{1,1} \times 2$$

$$dp[1][1][1] = a_{1,m}\times 2$$

最终的答案为：

$$\max\limits_{i=1}^{2}\{dp[n][i][m]\}$$

时间复杂度为 $O(n^2m^2)$，可以通过本题。

下面是记忆化搜索的 C++ 代码实现：

相关问题

{"mIcmDeviceIdDtoList":[{"id":3937237,"model":"X4","deviceId":"OPID000","line":"1","stationType":null,"stationCode":"ZD02","stationTypeDesc":"This MS","stationFocusType":"B","goal":0,"stage":"PAM","stageGroup":"PAM","stationSeq":"1","samelineFlag":"N","samelineShift":null,"enabled":"Y","createTime":"2023-06-02","createEmpno":"帅帅王","upDateTime":"2023-06-02","upDateEmpno":"admin","property01":0,"property02":0,"property03":null,"property04":null,"property05":null,"property06":null,"property07":null,"property08":null,"property09":null,"property10":null,"micmDeviceIdDtoList":null}]} 后端使用一个对象里面一个list属性接收不到

根据你提供的信息，这个 JSON 数据包含了一个名为 "mIcmDeviceIdDtoList" 的列表，其中包含了一个对象，该对象有多个属性。如果后端使用一个对象来接收这个 JSON 数据，可以使用以下代码：

public class MyObject {
    private List<MyItem> mIcmDeviceIdDtoList;

    // getter and setter methods
}

public class MyItem {
    private int id;
    private String model;
    private String deviceId;
    private String line;
    // 其他属性

    // getter and setter methods
}

在后端代码中，你可以使用一个 `MyObject` 对象来接收这个 JSON 数据，然后使用 `getMIcmDeviceIdDtoList()` 方法获取包含的列表。每个列表项都是一个 `MyItem` 对象，可以使用 `getId()`、`getModel()`、`getDeviceId()` 等等方法来获取其属性的值。在接收 JSON 数据时，需要使用框架或者库来进行反序列化，将 JSON 数据转换为后端的 Java 对象。常用的框架包括 Jackson、Gson 等等。