题解 P4954 【[USACO09Open] Tower of Hay 干草塔】
emptysetvvvv
·
2019-08-26 19:02:33
·
题解
单调队列 动态规划
背景
小萌新 \varnothing 初遇此题是在模拟赛上，私以为数据很水，果断贪心.......
思路
相信很多人看到此题会想到贪心：让高层尽可能的小 ，从后往前倒叙贪心。
方面起见，我们倒叙读入，从前向后贪心使每段尽可能的小。
那么可以枚举 第一层由 a[1]\sim a[i] 构成，设从前往后到了 a[i] ，当前层的宽度为 w ，那么就从 i 再往前后连续一段，使得这一段的长度恰好大于 w 。
对 a[i] 求前缀和 s[i] ，也就有了以下的代码：
for(int i = 1; i <= n and s[i]*ans <= s[n]; ++i) {
int w = s[i], cur = i, pre, cnt = 1;
while(s[cur] + w <= s[n]) {
pre = cur;
cur = lower_bound(s+cur+1, s+n+1, s[cur]+w) - s;
w = s[cur] - s[pre];
++cnt;
}
ans = max(ans, cnt);
}对于随机数据还是表现很不错的，但随手卡一下就会挂掉。
举个例子：
6
9 8 2 1 5 5
倒叙之后是 5\ 5\ 1\ 2\ 8\ 9 ，贪心划分结果为 5\ |\ 5\ |\ 1\ 2\ 8\ 9 共三层，然而正确答案是 5\ |\ 5\ 1\ 2\ |\ 8\ |\ 9 共四层。
可以看出，贪心错误之处在于 前面的贪心使得 底层过大，难以扩展。
我们大胆猜测，有一个较为贪心的结论：
构成最优解的若干种方案中，一定有一种满足底层最小 ，即 底层最小的方案 一定可以 构造出最高的层数 。
此结论由 ZKW 大神严谨证明。
一样，我们先把 a 数组翻转过来，前缀和为 s[i] 。
转移方程：
$$f[i]=f[j]+1(\text{ $j$ 为满足 } j\in[0,i-1]\text{ 且 } g[j]\leqslant s[i]-s[j] \text{的最后一个 }j)$$
要求最后一个 $j$ 是由于我们想要此时最后一层的宽度尽可能的小，得到 $j$ 后有 $g[i]=s[i]-s[j]$，
边界条件 $f[0]=0$。
转移复杂度 $O(n)$，总复杂度 $O(n^2)$。
- 考虑单调队列优化
转移条件为 $g[j]\leqslant s[i]-s[j]$，即 $g[j]+s[j]\leqslant s[i]$，那么就会有一个显然的结论：
若有 $k<j$ 且 $g[k]+s[k]\geqslant g[j]+s[j]$，则 $k$ 永远不可能再转移别人了，因为如果 $k$ 满足转移条件，那么 $j$ 也会满足，而 $j$ 的位置还更加靠后。
因此，我们可以维护一个 $g+s$ 值单调递增的 单调队列。
每次转移时从 单调队列中找到 最后一个 $g[j]+s[j]\leqslant s[i]$ 的位置 $j$，单调队列中 $j$ 以左的元素从队首出队。
转以后从队尾弹出 $g[j]+s[j]\geqslant g[i]+s[i]$ 的元素，然后将位置 $i$ 加入单调队列。
每个元素进出队列各一次，复杂度 $O(n)$。
### 代码
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005;
int n, a[maxn], s[maxn], f[maxn], g[maxn];
int q[maxn], l, r;
int main() {
scanf("%d", &n);
for(int i = n; i; --i) scanf("%d", a+i);
for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];
for(int i = 1; i <= n; ++i) {
while(l < r and s[q[l+1]]+g[q[l+1]] <= s[i]) ++l;
f[i] = f[q[l]] + 1;
g[i] = s[i] - s[q[l]];
while(l < r and s[q[r]]+g[q[r]] >= s[i]+g[i]) --r;
q[++r] = i;
}
printf("%d\n", f[n]);
return 0;
}
```