【黑历史】一个迟来七年的AC


没错,这就是难度Medium的换硬币。

每日一题翻到的,上次提交还是2015年。

刚看到满脸不屑,这不是教科书般的贪心么,吃着面包两三行代码搞定。

果断WA了。

看看case想了想,嗯,RMB可以贪心是因为有一块钱兜底,怎么贪心都能兜回来;这个题奇奇怪怪的case,很容易出现贪心了凑不出来的情况。

そうですね

暴力搜索肯定不行,看看15年的一大排TLE就知道了。

这个难不倒我,暴力搜索不行那带剪枝试试。于是我按照余数的循环对每一个硬币数量做了个基于贪心的剪枝。

。。。。。。然后发现这个剪枝,手滑会触发很多corner case不说,会剪掉正确的case。。。。!!

生无可恋了

。。。。。。

翻了翻题目,amount有上界,那就只剩下带状态的搜索/动规方法了。

于是我灵光一现,写出了个二维的状态方程。

。。。。。。

虽然直觉上感觉不对,但还是沉没成本+侥幸心理,在本地砍掉无用运算+预计算,把时间大约砍掉了一小半。

。。。。。。还是TLE了

瘫在椅子上,仔细一想,这。。。特么就就是个一维状态的动规啊,吐血了。。。。。。

翻了翻15年提交的代码,发现心路历程和这次是差不多的,一声叹息。

代码我都不好意思贴,黑历史啊黑历史:(



——此处是内容的分割线——

除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.utopiafar.com/2022/05/21/finally_got_an_ac_after_7_years/

码字不易,如果觉得内容有帮助,欢迎留言or点赞!

,

发表回复

您的电子邮箱地址不会被公开。