谁能给我解释一下题目?

P1569 Generic Cow Protests

本题类似于最长子序列的问题。 设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位之和为负,不可能有解。
by captainbear @ 2016-12-12 21:38:22


|