C++ 实现取数游戏最大得分算法

C++ 代码实现取数游戏最大得分算法

题目描述

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

输入格式

从标准输入读入数据。第一行输入一个正整数 n（n≤100）。接下来 n 行，每行输入 n 个正整数 aij（aij≤106），构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
int n,a[N][N],f[N],ans;
int main(){
    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++)
            f[j]=max(f[j],f[j-1])+a[j][i]*i;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}

算法思路

使用动态规划求解，f[i] 表示前 i 列取数的最大得分，状态转移方程为 f[i] = max(f[i], f[i-1]) + a[j][i] * i，表示当前列的取数得分加上前 i-1 列的最大得分，并取最大值。最后，遍历 f 数组，取最大值即为 n 轮取数的最大总得分。

优化说明

本代码使用滚动数组优化空间复杂度，仅需要一个大小为 n 的数组 f 来存储状态，节省了空间。

代码说明

N：定义矩阵大小上限
n：矩阵大小
a[N][N]：存储矩阵元素
f[N]：动态规划数组，存储前 i 列取数的最大得分
ans：存储最大总得分

运行步骤

输入矩阵大小 n 和矩阵元素 a[i][j]
使用动态规划算法计算 f 数组，并更新 ans 值
输出最大总得分 ans

总结

该代码实现了取数游戏的最大得分算法，使用了动态规划思想，简洁高效，易于理解。通过该代码，可以学习到动态规划算法的基本应用，以及如何优化代码的空间复杂度。