快乐的一天从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开始 | 20210803 | P3482


下一篇:干货|集中转发和本地转发,无线组网到底该怎么选?