自动搬运

查看原文

来自洛谷，原作者为

	xvhuanlin None

搬运于2025-08-24 21:26:34，当前版本为作者最后更新于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位之和为负，不可能有解。