动态规划 dp 前缀和 -- 题解 P1569 【Generic Cow Protests】

jijidawang · 2020-03-25 13:37:45 · 题解

题意简述

将数列 a 分成几组，每组数字和 \ge 0，求最大组数

算法分析

考虑 dp。

设 sum_n=\sum\limits_{i=1}^na_i，即前缀和。

然后设 dp_i 记录 1\sim i 区间的最优解。

将 dp_i 遍历 1\sim n，当找到第 i 个数时，从 0\sim i-1 中找到第 j 个数，满足 add_i+add_j\ge0，如果更优，就更新 dp_i。

注意 dp_j 一定要是非负的，要不然不满足条件。

则：

对于任意 i,j 若满足 dp_j>0 且 sum_i-sum_j>0 那么：

清楚了之后，代码很好写。