zcmimi's blog

arrow_back排序共12篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先把所有0合成1个,所有正数合成一个,把负数(除了最大的那个负数之外的(如果负数个数为奇数)))合成一个

1.如果全是0

2.没有0

3.没有负数

4.没有正数

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

咋一看:

f[i][j] = MAX(f[i-1][j-1]+a[j]*i,f[i][j-1]+a[j]*j)

n \le 3 \times 10^5,。。。

。。。

那么其实这不是dp题,而是思维题

我们发现:

(s[r]-s[l])\times k +(s[r']-s[l'])\times(k-1)+...+s[r''']

s表示前缀和,g表示后缀和

相当于:

g[x_1]+g[x_2]+g[x_3]+...

那我们给后缀和排个序就可以了

注意:

答案里必须要有g_1,这就是为什么要g1加(1ll<<50)再答案减(1ll<<50)的原因

2/2
Search
search