矩阵取数游戏

题解

给一个 n 行 m 列的数组，把问题细分成 n 个相同的问题，一行 m 列的数组

现在需要求解的是对于 m 个元素，如何取使得最终的结果最大

进而推出了转移方程组，进行求解即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 100;
__int128 a[maxn];
__int128 dp[maxn][maxn];
__int128 solve(int n) {
    for (int i = 0; i <= n; ++ i) {
        for (int j = 0; j <= n; ++ j) {
            dp[i][j] = 0;
        }
    }
    __int128 ans = 2;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j < i; ++ j) {
            dp[i][j+1] = max(dp[i-1][j]+ans*a[j], dp[i][j+1]);
        }
        for (int j = 0; j < i; ++ j) {
            dp[i][j] = max(dp[i-1][j]+ans*a[n-(i-j)], dp[i][j]);
        }
        ans = ans * 2;
    }
    __int128 maxx = 0;
    for (int i = 0; i < n; ++ i) {
        maxx = max(maxx, dp[n][i]);
    }
    return maxx;
}
__int128 InInt(int x) {
    __int128 y = 0;
    if (x == 0) return y;
    y = InInt(x/10);
    y = y * 10 + x % 10;
    return y;
}
void OutInt(__int128 x, bool flag) {
    if (x == 0 && !flag) return;
    OutInt(x/10, false);
    cout << int(x%10);
    if (flag) cout << endl;
}
int main() {
    int n, m, x;
    __int128 maxx = 0;
    cin >> n >> m;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            cin >> x;
            a[j] = 0;
            a[j] = InInt(x);
        }
        maxx += solve(m);
    }
    OutInt(maxx, true);
    return 0;
}