C/C++教程

快乐的一天从AC开始 | 20210802 | P2034

本文主要是介绍快乐的一天从AC开始 | 20210802 | P2034,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

每日吐槽

新功能在自己手机上测试没问题,用mentor的手机测就歇逼

查了一天,结果是硬件不同的问题,然后用的库识别不出来,人晕了

幸好库是公司维护的,还能魔改,不然麻烦就大了

心路历程

我怎么连蓝题都做不出来了啊

思路

应该一眼就能看出是DP

然后题目逆向转换一下,变成每\(k + 1\)个数中必须有一个数被删除,然后DP求满足条件的最小和,最后再用总的和减一下就是答案了。

然后怎么DP呢?对于每一个数,如果选他,那么在他之前的\(k\)个数中必须要删除一个,记\(f_i\)为删\(i\)的最小值,那么\(f_i = a_i + \min_{i - k - 1}^{i - 1} f_i\)。

然后就是单调队列板子题了

这篇关于快乐的一天从AC开始 | 20210802 | P2034的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!