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

## 题意简述 > 将数列 $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$ 那么： $$dp_i=\max\{dp_i,dp_j+1\}$$ 清楚了之后，代码很好写。