题解 P1564 【膜拜】

JOHNKRAM · 2013-10-01 23:52:26 · 题解

将2改为-1，题目就变成了将序列最少分为多少段，使每段和的绝对值≤M。

用简单的动态规划。

f[i]=max{f[j]}+1(|Σak|≤M) O(n²),轻松秒杀