竞赛讨论区 > 【每日一题】8月11日题目精讲—矩阵消除游戏

【每日一题】8月11日题目精讲—矩阵消除游戏

头像
西西莉
编辑于 2020-08-11 11:59:48 APP内打开
赞 0 | 收藏 0 | 回复19 | 浏览812

题号 NC200190
名称 矩阵消除游戏
来源 牛客练习赛58
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

—————————————以下就是一堆分析(废话)的分隔线—————————————
首先,我们很容易得到,先选哪一行(列),后选哪一行(列),只要选的一样是不影响结果的,这个我相信大家都能看出来啦……
第二,如果只按行选,或者只按列选,贪心妥妥的(把合最大的几行加起来就ok啦)。
第三,也是本题第一个问题:如果只按列选或者只按行选没有交叉就一定是最大值吗?
——没有交叉只能保证选的数字最多,但是未必的最大的,例如:
3 3 2
1 5 1
5 5 5
1 5 1
第四,如果我每次贪心的选剩下的图中最大的一行或者一列,然后把这一行(列)抹为0可以吗?(既按照题目描述步骤每一步贪心,这样的局部最优解能得到全局最优解吗?)
我想这又是一个可能会坑到的地方。
先也给一组反例:
4 4 3
1 1 9 3
1 8 10 8
1 2 7 2
1 2 2 2
一步一步贪心话先选第三列,第三列清零;然后选第二行,最后选第四列。但是选第二三四列更好哇。这是为什么?为什么这样贪心不对?
——因为你的每次选择,选一列也好选一行也好,会对后面的选择造成影响,且不同的选择造成的影响是不一样的,你这次先选了最好的一行(列)有可能就会使得后面能选的变少,你没选最好的一行(列)后面的机会却更多,这就是不满足无后效性,就好像装箱问题:给你一个体积为V的箱子,再给你若干件体积不同的物品,希望选一些物品尽量装满,你会上来就选择最大的吗?我们会很容易的想到,也许拼两个小的比装一个大的更好。对于做个题其实也一样,你选了最大的,后面选的就少了……
再多说两句,当你有这种怀疑却不知道对不对的时候怎么办呢?
严肃认真的方法是争取数学证明……但是这个方法我其实不太推荐,因为在贪心的方法对的时候,归纳法一般比较好证,但是要归纳法你没证明出来你就能说他不对吗?完全有可能是因为不会证……
那么在没法证明又怀疑的时候最好的办法是举反例,举反例不是随便举例子,是要从你的怀疑入手。以本题为例,什么情况容易出现反例?我怀疑的就是某一行或者列有几个数特别大,然后第一次就把他们一起选了,然而事实上可以通过后面的选择分开选这几个数。有了这种怀疑之后,你可以轻轻松松举出一堆反例,如:
3 3 2
100 100 1
2 4 2
4 2 2
还有一个稍微取巧一点的事情就是去看一下数据范围,这个不绝对,但是确实有提醒的作用。你看如果按上述方法贪心,时间复杂度是,这个题的nm都是15,也太小了,牛客这么好的服务器,如果这样可以那出题人为啥不把数据造大一点?

—————————————以下就是本题解法的分隔线—————————————
我们知道如果只是行的选择或者只是列的选择就可以贪心。那么我们就把问题转化成只选若干列好了!
如果我们想贪心的选取最好的若干列,那么我们必须提前知道我们选了多少行哪些行,这个怎么知道呢?看看数据范围,其实暴力就好了——写个搜索,或者用01串枚举。
所谓01串枚举,就是我们在每个个体都面对两种选择的时候,可以用一个01串表示,比如说对于本题,每一行有选和不选两种可能,假设有5行的话,我们就可以用一个长度为5的01串来表示,0表示不选1表示选,就像一个bool数组一样,如:01001 表明第134行不选,第25行要选。
只是用一个数字来表示比用数字表示方便,为什么方便呢?因为所有长度小于n的01串,转成十进制之后就是所有小于的数字,这样从0到−1枚举数字就是从00…00枚举到11…11。
具体细节在代码里面有注释:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44658550&returnHomeType=1&uid=554662

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目9月1日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

19条回帖

回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐