题目

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

输入描述：
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。

输出描述：
输出一个整数，即输入矩阵取数后的最大得分。

解析

1）知识点

  1. 这道题其实也没用到啥，可以看作就是一个没有那么简单的递归题。
  2. dfs遍历就好了，为了加快速度，我们要用记忆化搜索（备忘录法）。
  3. 这道题很大，需要用到高精度，但是我们可以用__int128简单的搞。

2）看题目

  1. 我们首先看题目说，我们每次要从两头选一个数字进行操作。
  2. 所以我们就简单的对两头选最大的就好了，就暴力的dfs遍历（从数据范围小也可以看出来）。

3）算法分析

  1. 这道题要说算法其实也没什么算法，因为高精度可以用__int128代替，其他就是暴力了。
  2. 我们知道，因为每一行是独立的，所以可以求出每一行的大小再加起来啦。
  3. 简单的说一下怎么暴力吧：
    1. 我们就是递归的算出左边和右边的值。
    2. 然后选取出两边最后求和比较大的一组返回就行了。
  4. 这里我们用一个dp数组对区间的最大值进行保存。用于减少相同的区间的大量重复计算。

4）算法操作

  1. 那我们先看一下怎么暴力，首先是递归计算左右的值： 
    big left = ((big)1 << move) * info[l] + dfs(l + 1, r);//选取左边的值
big right = ((big)1 << move) * info[r] + dfs(l, r - 1);//选取右边的值
    这里的题目要求是乘上2^i，所以我们可以直接用移位运算符来计算，同时计算也会快很多。
    注意move的算法： 
    int move = l - 1 + m - r + 1;//左移，左边删除的位数+右边删除的位数，相当于乘上2^i
  2. 然后我们看一下返回的情况： 
    return dp[l][r] = max(left, right);//返回最大值用于累加出最大值
  3. 同时我们还要注意递归结束的条件： 
    if (l > r) return 0;
  4. 这里再特判一下，如果备忘录已经几率过这个值的情况（就可以直接返回这个记录值了）： 
    if (dp[l][r]) return dp[l][r];

5）打代码

  1. 打代码咯~
  2. 所以其实就是先输入行列值。
  3. 然后一行一行输入呗。
  4. 每一行进行一个dfs然后加起来。
  5. 看我代码咯~

AC代码 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef __int128 big;
#define IOS ios::sync_with_stdio(false);

const int MAX = 87;
int n, m, info[MAX];//矩阵的长和宽
big dp[MAX][MAX];//行数组，备忘录数组

template<class T> inline void read(T& res);
template<class T> inline void write(T res);
big dfs(int l, int r);

int main() {
    read(n); read(m);
    big ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) read(info[j]);
        memset(dp, 0, sizeof dp);
        ans += dfs(1, m);
    }
    write(ans); putchar(10);
    return 0;   
}
template<class T> inline void read(T& res) {
    char c; int flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
template<class T> inline void write(T res) {
    if (res < 0) {
        putchar('-');
        res = -res;
    }
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
big dfs(int l, int r) {
    if (l > r) return 0;
    if (dp[l][r]) return dp[l][r];
    int move = l - 1 + m - r + 1;//左移，左边删除的位数+右边删除的位数，相当于乘上2^i
    big left = ((big)1 << move) * info[l] + dfs(l + 1, r);//选取左边的值
    big right = ((big)1 << move) * info[r] + dfs(l, r - 1);//选取右边的值
    return dp[l][r] = max(left, right);//返回最大值用于累加出最大值
}