Rise in Price

因为题目保证数据随机，根据官方题解所说，我们只需要维护当前状态最大的前几个状态，最终答案大概率就在这些状态中，我们每次保存从上次状态转移来的前\(100\)个最大状态，不断进行维护即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e2 + 5;
typedef pair<int, int> PII;
vector<PII> dp[MAXN][MAXN]; // pair存储每个状态的钻石个数和单价
int a[MAXN][MAXN], b[MAXN][MAXN];
int calc(PII p) {
    return p.first * p.second;
}
void solve(int x, int y, vector<PII> &X, vector<PII> &Y, vector<PII> &Z) {
    int i = 0, j = 0;
    while ((i < X.size() || j < Y.size()) && Z.size() < 100) {
        if (i < X.size() && j < Y.size()) {
            Z.push_back(calc(X[i]) > calc(Y[j]) ? X[i++] : Y[j++]);
        }
        else if (i < X.size()) {
            Z.push_back(X[i++]);
        }
        else if (j < Y.size()) {
            Z.push_back(Y[j++]);
        }
    }
    for (auto &it: Z) {
        it.first += a[x][y];
        it.second += b[x][y];
    }
}
bool cmp(PII lhs, PII rhs) {
    return lhs.first * lhs.second > rhs.first * rhs.second;
}
signed main(int argc, char *argv[]) {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> a[i][j];
                dp[i][j].clear(); // 多组数据记得初始化
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> b[i][j];
            }
        }
        dp[1][1].push_back({a[1][1], b[1][1]});
        for (int i = 2; i <= n; ++i) { // 预处理第一行
            auto it = dp[1][i - 1][0];
            dp[1][i].push_back({it.first + a[1][i], it.second + b[1][i]});
        }
        for (int i = 2; i <= n; ++i) { // 预处理第一列
            auto it = dp[i - 1][1][0];
            dp[i][1].push_back({it.first + a[i][1], it.second + b[i][1]});
        }
        for (int i = 2; i <= n; ++i) {
            for (int j = 2; j <= n; ++j) {
                solve(i, j, dp[i - 1][j], dp[i][j - 1], dp[i][j]);
                sort(dp[i][j].begin(), dp[i][j].end(), cmp); 
            }
        }
        int res = 0;
        for (auto it: dp[n][n]) {
            res = max(res, it.first * it.second);
        }
        cout << res << '\n';
    }
    system("pause");
    return 0;
}