题解：P14242 [CCPC 2024 Shandong I] 分割序列

· · 题解

思路

这道题我们看上去很像是动态规划，于是我们设 dp_{i,j} 表示 k 为 i 时，考虑了前 j 个数字时的最大答案。

发现空间复杂度为 O(n ^ 2)，炸飞了。

于是我们分析一下题目。

不难发现：每个数字至少会被加进答案一次。而一个数字如果会被加进答案两次，那么一定会是第一次的答案再加上这个数的值。即 k 等于 1 时，答案为全部数字相加，然后，k 等于 2 时，答案一定为 k 等于 1 时的答案加上某一个后缀和。

发现这个有什么用呢，我们可以退出来一个结论：每一次的结果一定是上一次的答案加上。

于是，我们一开始求出后缀和，然后排序去求解即可。

代码不难。

for (int i = 1;i <= n;i++) read(a[i]);
        for (int i = n;i > 0;i--) f[i] = f[i + 1] + a[i];
        cnt = f[1],sort(f + 2,f + n + 1),write(cnt),putchar(' ');
        for (int i = n;i > 1;i--) cnt += f[i],write(cnt),putchar(' ');
        putchar('\n');