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

思路

这道题我们看上去很像是动态规划，于是我们设

dp_{i,j}

表示

k

为

i

时，考虑了前

j

个数字时的最大答案。

发现空间复杂度为

O(n ^ 2)

，炸飞了。

于是我们分析一下题目。

不难发现：每个数字至少会被加进答案一次。而一个数字如果会被加进答案两次，那么一定会是第一次的答案再加上这个数的值。即

k

等于

1

时，答案为全部数字相加，然后，

k

等于

2

时，答案一定为

k

等于

1

时的答案加上某一个后缀和。

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

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

代码不难。

CPP

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');

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

文章操作

思路

相关推荐

评论

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