【每日一题】 矩阵取数游戏 题解

Description

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * ，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

Solution

这种题目描述，包含了很多决策状态，肯定是动态规划来做的。由于每一行是独立的，不会相互影响，那么对每一行都取最优决策即可。
我们令 为当前行取[i,j]区间能得到的最优值，显然有递推式
显然有递推式，
对每行做上述dp，通过记忆化搜索保证每个状态只访问一次，这里需要使用高精度，跟zzugzx偷学了一手python

Code

while True:
    try:
        n, m = map(int, input().split());
        dp = [[0 for i in range(81)] for i in range(81)]; 
        a = [0 for i in range(n + 1)];
        def solve(l, r):
            p = r - l + 1;
            k = m - p + 1;
            if dp[l][r] :
                return dp[l][r];
            if l == r :
                return a[l] * (2 ** k);
            dp[l][r] = max(solve(l + 1, r) + a[l] * (2 ** k), solve(l, r - 1) + a[r] * (2 ** k));
            return dp[l][r];
        ans = 0;
        for i in range(n):
            dp = [[0 for i in range(100)] for i in range(100)];
            a = list(map(int, input().split()));
            ans += solve(0, m - 1);
        print(ans);
    except EOFError:
        break