P2300 合并神犇
设fi表示合并了前i个合法的最小步数
gi表示前i个合法的最小的最后一个神犇
那么一个n^2的做法就是i从最近的合法的j转移过来
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(i=1;i<=n;i++)
{
for(j=i-1;j>=0;j--)if(sum[i]-sum[j]>=g[j])break;
f[i]=f[j]+i-j-1;
g[i]=sum[i]-sum[j];
}
printf("%lld\n",f[n]);
证明：
我们一定选择的是从j2转移过来，考虑假设j1被分成了x段，那么j2有和他相同的前缀，那么最少也就是x段（把不同的都丢到最后一个里面），况且还可能自成若干段（也就是说相同的序列，往一个后面再加若干个数，那么那个分成的段数一定是大于等于不加分成的段数的），而且j2到i还小于j1到i，明显更优
因为数据随机n^2已经足够过题，on就是单调队列优化一下