题解 P1569 【[USACO11FEB]属牛的抗议Generic Cow Prote…】

xvhuanlin · 2015-03-16 02:00:34 · 题解

本题类似于最长子序列的问题。

设add数组记录前i个数的和，dp数组记录分组到第i数时的最大分组。

当add[n]<0时，直接输出Impossible。

不然从1到n循环，当找到第i个数时，从0到i-1中找到第j个数，满足add[i]-add[j]>=0，即保证j到i为一组时，和是非负的，若dp[j]+1>dp[i]，则更新dp[i]。

需要注意的是，找到第i个数时，必须保证add[i]>=0，反之跳到下一位。因为若add[i]<0，则此时前i位之和为负，不可能有解。