【ybtoj高效进阶 21261】头文字 C（单调队列优化DP）

头文字 C

题目链接：ybtoj高效进阶 21261

题目大意

给你一个数组，然后问你最多能分成多少段，使得每一段的值不增。
每一段的值是这一段的数的和。

思路

首先我们把序列翻转，变成要单调不降。

然后考虑 DP，设 (f_{i,j}) 为把前 (i) 个数最多能分成多少段（最后一段是 (j+1sim i)）。
那不难得到一个 (O(n^3)) 的转移：(f_{i,j}=sumlimits_{k<j,S_j-S_kleqslant S_i-S_j}{f_{j,k}+1})

然后我们考虑优化，首先我们要想到一个性质，就是在上面的转移中同样的 (i,j)，如果两个 (k) 都可以转移，而且 (k_1<k_2)，那么 (k_2) 一定不会比 (k_1) 劣。
（因为你都可以转移了，我们肯定就是要缩小上一段的，让它恰好比这一段大一点，所以 (k) 能靠后就靠后）

那我们就可以进行一个优化，直接设 (f_{i}) 为搞定前 (i) 个数最多分成多少段。
然后用另一个数组 (suf_i) 记着最后一段的大小。
那我们就得到 (O(n^2)) 的转移：
(f_{i}=sumlimits_{j<i,suf_jleqslant S_i-S_j}{f_{j}+1})

稍微把条件移项一下有 (S_igeqslant suf_j+S_j)，发现 (S_i) 单调递增，决策的集合越来越大。
我们就维护一个 (j) 递增，(suf_j+S_j) 递增的单调队列即可。

代码

#include<cstdio>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

int n, a[100002];
int ans, suf[100002];
int f[100001], sta[100001];

int main() {
//	freopen("read.txt", "r", stdin);
//	freopen("block.in", "r", stdin);
//	freopen("block.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[n - i + 1]);
	
	for (int i = 1; i <= n; i++)
		a[i] += a[i - 1];
	
	int l = 1;
	sta[++sta[0]] = 0;
	for (int i = 1; i <= n; i++) {
		while (l < sta[0] && suf[sta[l + 1]] + a[sta[l + 1]] <= a[i]) l++;//找到最右的能满足的
		f[i] = f[sta[l]] + 1;//转移
		suf[i] = a[i] - a[sta[l]];//放进单调队列里面
		while (l <= sta[0] && suf[i] + a[i] <= suf[sta[sta[0]]] + a[sta[sta[0]]])
			sta[0]--;
		sta[++sta[0]] = i;
	}
	
	printf("%d", f[n]);
	
	return 0;
}