博客食用更佳~
https://www.cnblogs.com/czyty114/p/14824981.html
A
将a从小到大排序,显然a1,a2n,a2,a2n−1,⋯,an,an+1这样是满足条件的
总结:构造题
B
容易发现,对于1111,11111,111111,⋯这样的数都是可以用11,111凑出来的
所以考虑用11,111这两种数字
枚举11用了多少次,由于这玩意是有循环的,最多枚举到111就可以了
总结:找特殊性质+循环节
C
Easy
考虑dp
设计fi,j表示前i个选了j瓶药后能剩下的最大健康值是多少
转移显然就是fi,j=max1≤k<i(fk,j−1)+ai
边dp边处理最大值即可
Hard
考虑贪心
我们发现,按照药水值从大到小的顺序选,如果当前选会挂掉则跳过,否则就选这样的贪心策略一定是最优的
对于i<j,ai>aj显然我们会选择先去喝j
那i<j,ai<aj,如果先选了i,会不会导致不能选j而使答案更劣呢?
假设出我们不选i,就算之后能选j这瓶药水,选的药瓶数也是一样的(但此时会使健康值变得更小)
而我们选i是在保证不会挂的情况下的
所以这样就能满足选i一定是最优的
而判断是否会挂,我们假设fi是到i这个位置剩余健康值是多少。
每次选药水,我们只需要支持一个查询后缀最小值,和后缀+k的操作
这玩意我写了个线段树去维护
总结:发现无法用dp或很麻烦时,不妨去推有什么特殊的性质,或使用特殊的策略去贪心的解决问题