[Usaco 2009 Open]干草堆tower

把一个长为n的正整数序列划分为一些连续的段落, 使得每一段元素之和单调递增, 求最多段数. (1≤n≤10^5, 1≤wi≤10^4) 提到决策单调性, 学妹推荐了这道题. >_<

并不知道怎么把状态数降下来, 学习了一下题解.

第一段元素之和最小 => 段数最多.

网上题解的证明基本一样......并且都备注了转自zkw......

考虑两种方案, 第一种第一段最小, 第二种第一段不是最小的. 把第二种调整成第一种, 触发了一系列这样的操作: 把原第i段元素加入第(i+1)段. 调整结束后, 段数要么不变, 要么增加.

那么, 找最多的段数转化为了找最小的第一段. 设 为后缀 中第一段的最小值,

其中 是后缀和.

单调递增. 如果 , 那么仅当 时, 可能有用. 所以, 维护 单增, 单增的单调队列.

和滑动窗口略有不同. 在那个问题中, 下标是约束, 值是待求量. 这里, 值是约束, 下标是待求量. 在我的定义中, 下标是单调的那一维. >_<

const int N = 1e5 + 1;

int S[N], f[N], g[N], Q[N];

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 0, n)
		scanf("%d", S+i);
	per (i, n-2, 0)
		S[i] += S[i+1];
	int* p = Q, * q = Q+1;
	Q[0] = n;
	per (i, n-1, 0)
	{
		while (p != q && S[*p]+f[*p] <= S[i]) ++p;
		--p;
		f[i] = S[i] - S[*p];
		g[i] = g[*p] + 1;
		while (p != q && S[i]+f[i] < S[*(q-1)]+f[*(q-1)]) --q;
		*q++ = i;
	}
	printf("%d\n", g[0]);
	return 0;
}