查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转咋一看：$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……