这题搞了好久,大意是讲给一个长为n的数串,让其中某一个子区间的数都+k,然后使得整个串里等于c的数个数尽可能大,问最大多少
串里的数范围挺宽的,先想这个+k,实际上就是尽可能多的把不是c的变成c,尽量少把c变成其它的,要注意这里k选定了以后,能变成c的数就只有是c-k
由于串里的c一开始的数量是确定的,于是最终c的数量=原来c的数量+(变成了c的数的数量-变成了别的数的c的数量),其实我们就是要求括号里的最大值
dp
代码是我看了别人的提交后写的,感觉这里能想到dp的都是神仙吧,(这都什么人呀!!!!)
理解了这个dp后我才修好了我下面写的贪心
1 |
|
贪心
这题一开始考虑数据范围很大,二层三层循环啥的肯定gg,然后想到求一段给定数列的子区间和的最大值的方法,那种方法只要一次遍历数组不断更新前缀和的最小值,然后每次更新max(当前的前缀和-之前找到的最小值)
这里也效仿一下,对所有除了c以外出现的数都这么求
注意这里计算最小前缀和的时刻我放到了遇到t并处理之前,然后再计算当前前缀和,然后再相减更新结果
注意在这里k是有很多取值的(因为串里的数在一个情况下都能变成c),我们这里一并进行运算了,这些k的取值情况之间相互是没有联系的,具体的看代码吧
1 |
|