luoguP1005 矩阵取数游戏

有n*m的矩阵，每个元素a[i][j]均为非负整数，游戏规则如下：

1. 每轮从每行各取一个元素，共n个。经过m轮后取完所有元素。
2. 每次取走的元素只能是该元素所在行的行首或行尾。
3. 每轮取数都有一个分值，为每行取数的得分之和，每行取数的得分为被取走的元素值乘以2的i次方，其中i为取数轮次，从1开始。
4. 游戏结束时总得分为m轮取数得分之和。

求可以得到的最大得分。
1<=n,m<=80; 0<=a[i][j]<=1000

分析：加法满足交换律和结合律，可以分别考虑每行的最大得分，然后相加得到总得分，而每行取数就是个区间dp问题。结果很大，需要用高精。

#include <bits/stdc++.h>
using i64 = long long;

// bint模板...

int n, m, A[85][85];
bint p2[85];

void solve() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> A[i][j];
        }
    }

    p2[0] = 1;
    for (int i = 1; i <= m; i++) {
        p2[i] = p2[i - 1] * 2;
    }

    bint ans = 0;
    for (int k = 1; k <= n; k++) {
        bint dp[m + 1][m + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][i] = p2[m] * A[k][i];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = i - 1; j >= 1; j--) {
                dp[j][i] = std::max(dp[j][i], p2[m - i + j] * A[k][j] + dp[j + 1][i]);
                dp[j][i] = std::max(dp[j][i], p2[m - i + j] * A[k][i] + dp[j][i - 1]);
            }
        }
        ans += dp[1][m];
    }
    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}