简单的打击(众数)

题目大意:你什么方面都强,所以你可以分别重新锻造这两把剑,锻造就相当于重新排列这两个序列。合并这两把剑,让它变成一把新剑(对应序列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
2
3
4
5
6
7
8
9
10
for (i = 1; i <= maxv + 100; ++ i)
{
int res = 0;
for (j = 1; j <= i - 1; ++ j)
{
// res += min(a[j], b[i - j]);
res += min(b[j], a[i - j]);
}
yhm = max(yhm, res);
}