取数游戏：动态规划求解最大得分

题目描述

给出一个 $n \times n$ 的矩阵，进行取数游戏。 取数共 $n$ 轮，第 $i$ 轮需要从每行分别取一个没取过的数字，设取出的数字总和是 $s$，则第 $i$ 轮的实际得分是 $i \times s$。 求 $n$ 轮取数的最大总得分。

输入格式

从标准输入读入数据。 第一行输入一个正整数 $n$（$n \le 100$）。 接下来 $n$ 行，每行输入 $n$ 个正整数 $a_{ij}$（$a_{ij} \le 10^6$），构成一个矩阵。

输出格式

输出到标准输出。 输出一个整数，表示最大总得分。

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int a[105][105], f[105][105];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int mx = -0x7f7f7f7f;
            for (int k = 1; k < j; k++) mx = max(mx, f[i][k]);
            for (int k = 1; k < i; k++) mx = max(mx, f[k][j]);
            f[i][j] = mx + a[i][j];
        }
    int ans = -0x7f7f7f7f;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            ans = max(ans, f[i][j] * (n - i + 1));
    cout << ans << endl;
    return 0;
}