网课:第二章模拟、枚举与贪心---矩阵消除游戏

2024-05-08 23:52

本文主要是介绍网课:第二章模拟、枚举与贪心---矩阵消除游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

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

牛妹想最大化她的得分,球球你帮帮她吧!

输入描述:

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

输出描述:

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

示例1

输入

3 3 2
101 1 102
1 202 1
100 8 100

输出

414

备注:

1≤n,m≤151\leq n,m\leq 151≤n,m≤15

1≤ai,j≤1e61\leq a_{i,j}\leq 1e61≤ai,j​≤1e6

1≤k≤n∗m1\leq k\leq n*m1≤k≤n∗m

错误做法

把行的和与列的和放在一起从大到小排序,每次取最大的,并处理应该清0和减去的值,然后再从大到小排序。就是每次都贪心取最大的行或列。

这种做法是错的,例如这个样例:

4 4 2

400 10 10 9

0 0 0 0

0 0 0 0

400 11 2 400

按这个算法的话,会选择第一列和第四列。但是如果我们选第一行和第四行就能全部收割了。那么为什么这个算法是错的呢,因为我们每次的选择都会对之后的选择有影响,就是行会影响列,列会影响行,会有后效性。

正确解法

如果我们只贪心行或者只贪心列,那么就不会有影响。以只贪心列举例,我们可以枚举出哪行几行是取的,然后再用剩下可以取的数目来贪心列。那么就可以利用二进制枚举来枚举所有行的方案,再贪心列

待验证解法

我分两种情况。一是枚举行选的数目(0到k),然后贪心取大的那几行,然后剩下的数目贪心选取列。二是枚举列选的数目(0到k),然后贪心取大的那几列,然后剩下的数目贪心选取行。

#include<bits/stdc++.h>
using namespace std;
int h[20],l[20];
int n,m,k;
int jz[20][20];
struct ty{int pos,sum;  
};
bool cmp(ty a,ty b){return a.sum>b.sum;
}
vector<ty> r,c;
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){int sum=0;for(int j=1;j<=m;j++){scanf("%d",&jz[i][j]);sum+=jz[i][j];}h[i]=sum;r.push_back({i,sum});}for(int i=1;i<=m;i++){int sum=0;for(int j=1;j<=n;j++){sum+=jz[j][i];}l[i]=sum;c.push_back({i,sum});}sort(r.begin(),r.end(),cmp);int ans=0;//先选行,再选列for(int i=0;i<=k;i++){int res=0;for(int j=1;j<=i&&j-1<=n;j++){//处理选的行res+=r[j-1].sum;for(int u=0;u<m;u++){c[u].sum-=jz[r[j-1].pos][u+1];}}sort(c.begin(),c.end(),cmp);for(int j=1;j<=k-i&&j-1<=m;j++){//处理选的列res+=c[j-1].sum;}ans=max(ans,res);c.clear();r.clear();for(int j=1;j<=n;j++) r.push_back({j,h[j]});for(int j=1;j<=m;j++) c.push_back({j,l[j]});sort(r.begin(),r.end(),cmp);}c.clear();r.clear();for(int j=1;j<=n;j++) r.push_back({j,h[j]});for(int j=1;j<=m;j++) c.push_back({j,l[j]});sort(c.begin(),c.end(),cmp);//先选列再选行for(int i=0;i<=k;i++){int res=0;for(int j=1;j<=i&&j-1<=m;j++){//处理选的列res+=c[j-1].sum;for(int u=0;u<n;u++){r[u].sum-=jz[u+1][c[j-1].pos];}}sort(r.begin(),r.end(),cmp);for(int j=1;j<=k-i&&j-1<=n;j++){//处理选的行res+=r[j-1].sum;}ans=max(ans,res);c.clear();r.clear();for(int j=1;j<=n;j++) r.push_back({j,h[j]});for(int j=1;j<=m;j++) c.push_back({j,l[j]});sort(c.begin(),c.end(),cmp);}cout<<ans;
}

等我会对拍了就来验证一下

这篇关于网课:第二章模拟、枚举与贪心---矩阵消除游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/971797

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

国产游戏崛起:技术革新与文化自信的双重推动

近年来,国产游戏行业发展迅猛,技术水平和作品质量均得到了显著提升。特别是以《黑神话:悟空》为代表的一系列优秀作品,成功打破了过去中国游戏市场以手游和网游为主的局限,向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展,国产游戏正逐步赢得国际市场的认可。然而,面对全球游戏行业的激烈竞争,国产游戏技术依然面临诸多挑战,未来的

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi