牛客练习赛58 C.矩阵消除游戏

Wanda ·

更新时间:2024-09-21

· 948 次阅读

牛客练习赛58 C.矩阵消除游戏

题目链接

题目描述

牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n行m列，第i行第j列的单元格的权值为ai,ja_{i,j}ai,j ，牛妹可以进行k个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述:

第一行三个整数n,m,k
接下来n行每行m个整数表示矩阵中各个单元格的权值。

输出描述:

输出一个整数表示牛妹能获得的最大分数。

示例1 输入

输出

很多人一开始想暴力，但是实际上暴力是有问题的，比如我下面这个例子，假设n=m=3,k=2：
[132246378] \left[ \begin{matrix} 1&3&2\\ 2&4&6\\ 3&7&8\\ \end{matrix} \right] ⎣⎡123347268⎦⎤
暴力的话第一次可选第一行或者第一列，但出于最优考虑，只能选第一行和第三行，此时暴力就无法判断是否最优了，我们不妨换个角度：
1.列举出所有列的选举情况 2m2^m2m
2.计算剩下的每行的权值和并排序
3.将所选行与所选列相加，更新答案
4.重复上述步骤，直至最优
AC代码如下：

#include
using namespace std;
typedef long long ll;
int a[20][20],n,m,k,sum[20];
bool cmp(int a,int b){
    return a>b;
}
int count1(int n){
    int ans=0;
    while(n){
        ans++;
        n=n&(n-1);
    }
    return ans;
}
int main(){
    cin>>n>>m>>k;
    k=min(k,min(m,n));
    for(int i=0;i<n;i++){
        for(int j=0;j>a[i][j];
    }
    int ans=0;
    for(int i=0;i<1<k) continue;
        int res=0;
        for(int j=0;j<n;j++){
            for(int k=0;k<m;k++)
                if(1<<k&i) res+=a[j][k];//选中的列加到res里
                else sum[j]+=a[j][k];//计算行的权值和
        }
        sort(sum,sum+n,cmp);
        for(int j=0;j<k-cnt;j++) res+=sum[j];
        ans=max(ans,res);
    }
    cout<<ans<<endl;
}

作者：旺崽

牛客矩阵

1024 个赞