C++ 取数游戏算法：最大得分求解

C++ 取数游戏算法：最大得分求解

本算法解决了一个经典的取数游戏问题：给定一个n*n的矩阵，每轮从每行取一个数字，得分与取数的轮数和数字总和相关，求n轮取数的最大总得分。

题目描述

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

输入格式

从标准输入读入数据。 第一行输入一个正整数 'n' ('n ≤ 100')。 接下来 'n' 行，每行输入 'n' 个正整数 'a_ij' ('a_ij ≤ 10⁶')，构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,a[105][105],ans;
bool vis[105];
int main()
{
    scanf('%d',&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf('%d',&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        int mx=0;
        for(int j=1;j<=n;j++)
            if(!vis[j])
                mx=max(mx,a[i][j]);
        ans+=i*mx;
        for(int j=1;j<=n;j++)
            if(a[i][j]==mx)
                vis[j]=true;
    }
    printf('%d',ans);
    return 0;
} 

算法思路

该问题可以使用贪心算法解决。每次选择当前行中最大的未被选取的数字，并将该数字所在列标记为已选取。

代码解释

1. a[105][105]：存储输入矩阵的二维数组
2. ans：存储最终的最大得分
3. vis[105]：标记每列是否已被选取

代码遍历每一行，在每行中寻找最大未被选取的数字，将该数字加入总得分，并标记该数字所在列为已选取。

总结

本代码使用贪心算法，通过每次选择当前行中最大的未被选取的数字来求解取数游戏的最大总得分。代码简洁易懂，实现效率高。