Problem
随机 \(n\) 个正整数组成序列。将序列分尽量多的段数，使得前一段的和不大于后一段的和。求能分成多少段。输出 \(n-ans\)。\(n\leq 10^5\)，值域不重要。
Solution
状态设计为：\(f_i=1+\min_{sum_i-sum_j\geq g_j}f_j\) 表示前 \(i\) 个数字划分的最多段数，\(g_j\) 定义为 \(f_i\) 的转移点 \(j\) 上的 \(sum_i-sum_j\) 也就是在这一次划分中。单调队列优化 DP 即可。
下面证明：
-
\(f_i\) 单调不降，\(f_i-f_{i-1}\leq 1\)。
至少存在一种方案，是将 \(i\) 并入到最后一次划分的块中。另外还可能 \(a_i\) 单独成块。 -
对于 \(i<j\)，如果 \(f_i=f_j\)，那么 \(g_i<g_j\)。
错误证明：它们的决策点单调递增 -
我们总是找离 \(i\) 最近的合法的 \(j\)，这样会使得 \(g_i\) 最小。
可以参考一下 https://www.luogu.com.cn/blog/484784/p2300-ge-bing-shen-post#
Code
暴力能过
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int n;
LL sum[1<<18],f[1<<18],g[1<<18];
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
for(int i=1;i<=n;i++){
for(int j=i-1;j>=0;j--){
if(sum[i]-sum[j]>=g[j]){
f[i]=f[j]+1;
g[i]=sum[i]-sum[j];
break;
}
}
debug("f[%d]=%d,g[%d]=%d\n",i,f[i],i,g[i]);
}
printf("%d\n",n-f[n]);
return 0;
}