动态规划

题意:

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

输入描述:
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
输出描述:
输出一个整数，即输入矩阵取数后的最大得分。

分析:

首先一个重要的发现:
我们发现这一题其实和矩阵没有关系!!!
我们求矩阵最后的答案其实就是求每一行最后的答案再相加

这是个重要的发现,这意味着我们可以不管矩阵一说,直接关注对于一个数组如何去求题目条件中的最大值

看数组:
[a1,a2,a3,a4,a5,a6,a7,a8,a9]
我们想一想我可能取a1,那么接下来我将会在[a2,a3,a4,a5,a6,a7,a8,a9]中寻找答案
如果我取a9,那么接下来我将会在[a1,a2,a3,a4,a5,a6,a7,a8]中寻找答案
其实我们看到题目条件可以取行尾也可以取行末时,就应该意识到这很可能是个区间dp
给出状态
dp[i][j]表示在[i,j)中从2^1开始的最大值
状态转移方程:
dp[i][j] = max(2^1input[i]+2dp[i+1][j],2^1input[j-1]+2dp[i][j-1])

注意到数组遍历比较困难,所以我们选择记忆化搜索.

ll solve(int l,int r) 
{
    if (dp[l][r] != -1)return dp[l][r];
    if (r - l == 1)return dp[l][r] = (ll)in[l] * 2;
    return dp[l][r] = max(solve(l + 1, r) + in[l], solve(l, r - 1) + in[r-1]) * 2;
}

但是,重要的是数据范围超过了long long了,所以最简单的直接用python吧

代码如下,注意细节

max_n = 100
a = [0 for i in range(max_n)]
dp = [[-1 for j in range(max_n)] for i in range(max_n)]
n = 0
m = 0

def solve(l,r):
    if dp[l][r] != -1:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = a[l] * 2
    else:
        dp[l][r] = max(solve(l + 1, r) + a[l], solve(l, r - 1) + a[r - 1]) * 2
    return dp[l][r]


n,m = map(int,input().split())
ans = 0
for i in range(1,n+1):
    s = input().split()
    for j in range(len(s)):
        a[j+1] = int(s[j])
    dp = [[-1 for j in range(max_n)] for i in range(max_n)]
    ans+=solve(1,m+1)
print(ans)