简单的打击(众数)
题目大意:你什么方面都强,所以你可以分别重新锻造这两把剑,锻造就相当于重新排列这两个序列。合并这两把剑,让它变成一把新剑(对应序列c),合并相当于把对应位置上的数加起来c[i]=a[i]+b[i]。最后你准备拿着这把新剑去找大Boss,造成的伤害是众数出现的次数。问怎么排列才能使得伤害最大化,输出最大伤害
考虑正解是ntt什么玩意的
考虑可以拿满分的dp暴力
我们发现权值都特别小,才一万,所以我们可以开一个桶来记录
然后我们对所有数取一个最大值
然后dp枚举\(\sum min(a[j],b[i-j])\)
其中i为我们枚举的众数,j即为考虑有没有这个数字
正常的话,我们枚举的上限是\(10000+10000\)
所以时间复杂度是\(O(20000*20000)\)
但是我们忙猜概率不会那么大,我们只去枚举到最大值加上一个随机数字(小于五百)
然后就可以过了….
代码:
1 | for (i = 1; i <= maxv + 100; ++ i) |