体育课上，n个小朋友排成一行（从1到n编号），老师想把他们分成若干组，每一组都包含编号连续的一段小朋友，每个小朋友属于且仅属于一个组。
第i个小朋友希望它所在的组的人数不多于d[i]，不少于c[i]，否则他就会不满意。
在所有小朋友都满意的前提下，求可以分成的组的数目的最大值，以及有多少种分组方案能达到最大值。
朴素dp方程并不难,dp[i]表示到第i个人正好划分成dp[i]组,可以从一定范围内满足条件的j(j<i)通过dp[i]=max(dp[j-1]+1)得到
这样的复杂度是n^3
可以用分治优化dp
每层分治(以solve(l,r)表示)不能无脑地以中点作为划分
而是要找到一个以l到r C最大的点作为划分点k
我们每层分治的任务就是处理l-->k对k-->r的贡献(0到l-1的已经处理过了)
原文：https://www.cnblogs.com/lnxcj/p/10360276.html