取数游戏 - C++ 代码实现 - 常规

取数游戏 - 动态规划 C++ 代码实现

题目描述

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

输入格式

从标准输入读入数据。第一行输入一个正整数 n（n <= 100）。接下来 n 行，每行输入 n 个正整数 a[i][j]（a[i][j] <= 10^6），构成一个矩阵。

输出格式

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

样例

样例输入 #1

样例输出 #1

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e9 + 5;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T,n,a[N][105],f[N][105];
signed main(){
    IOS;
    cin>>n;
    rep(i,1,n)rep(j,1,n)cin>>a[i][j];
    rep(i,1,n)f[0][i]=-INF;
    rep(i,1,n)rep(j,1,n)f[i][j]=-INF;
    rep(i,1,n){
        rep(j,1,n){
            rep(k,1,n){
                if(i+j==k) f[k][i]=max(f[k][i],f[k-i][j]+a[i][k-i+1]+a[j][k-j+1]*i);
            }
        }
    }
    ll ans=0;
    rep(i,1,n)ans=max(ans,f[n][i]*i);
    cout<<ans<<'\n';
    return 0;
}

代码解释

状态定义: f[i][j] 表示前 i 轮取数，且第 i 轮从第 j 行取数时的最大得分。
状态转移:
- f[0][i] = -INF：初始状态，没有进行取数，得分设为负无穷。
- f[i][j] = max(f[i][j], f[i-k][j-1] + a[k][i-k+1] + a[j][i-j+1] * i)：表示从第 k 行取数，f[i-k][j-1] 表示前 i-k 轮取数的得分，a[k][i-k+1] 是第 k 行第 i-k+1 列的数字，a[j][i-j+1] 是第 j 行第 i-j+1 列的数字，i 是当前轮数。
边界情况: 第 i 轮只能从第 i 行开始取数，因此 f[i][j] = -INF 当 j < i 时。
最终答案: 遍历 f[n][i]，找到最大得分即可。

总结

这道题使用动态规划的方法进行求解，状态转移方程是关键。代码简洁易懂，便于理解和实现。

取数游戏 - C++ 代码实现