BZOJ1233. [Usaco2009Open]干草堆tower（单调队列dp）

本文主要是介绍BZOJ1233. [Usaco2009Open]干草堆tower（单调队列dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
奶牛们讨厌黑暗。为了调整牛棚顶的电灯的亮度，Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草（1<=N<=100000）(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1. Bessie必须利用所有N包干草来建立起干草堆，并且按照他们进牛棚的顺序摆放。她可以相放多少包就放多少包来建立起tower的地基（当然是紧紧的放在一行中）。接下来他可以放置下一个草包放在之前一级的上方来建立新的一级。注意：每一级不能比下面的一级宽。她持续的这么放置，直到所有的草包都被安置完成。她必须按顺序堆放，按照草包进入牛棚的顺序。说得更清楚一些：一旦她将一个草包放在第二级，她不能将接下来的草包放在地基上。 Bessie的目标是建立起最高的草包堆。

Input
第1行：一个单一的整数N。第2~N+1行：一个单一的整数:W_i。

Output
第一行：一个单一的整数，表示Bessie可以建立的草包堆的最高高度。

Sample Input
3
1
2
3

Sample Output
2
输出说明：
前两个（宽度为1和2的）放在底层，总宽度为3，在第二层放置宽度为3的。
±---------+
| 3 |
±–±-----+
| 1 | 2 |
±–±-----+
Hint
Source

思路：
贪心的选取每层宽度，宽度越窄相对越优。
先逆序输入，题目变成分成连续数块单调不下降。

定义g[i]为选到了第i个草堆的宽度，f[i]为选到第i个草堆的最大高度
s[i] - s[j] >= g[j]时，可以有f[i] = f[j] + 1。（j < i）。此时满足，g[j]越小越好，也就是说s[j] + g[j]越小越好。
那么我们需要维护的就是s[j] + g[j]，维护一个单调递增队列，每次选出最小的s[j] + g[j]对应的j即可。

#include <cstdio>using namespace std;const int maxn = 100000 + 7;int q[maxn],g[maxn],f[maxn],a[maxn],s[maxn];int main()
{int n;scanf("%d",&n);for(int i = n;i >= 1;i--){scanf("%d",&a[i]);}for(int i = 1;i <= n;i++){s[i] = s[i - 1] + a[i];}int l = 1,r = 0;for(int i = 1;i <= n;i++){while(l <= r && s[i] >= g[q[l]] + s[q[l]])l++;g[i] = s[i] - s[q[l - 1]];f[i] = f[q[l - 1]] + 1;while(l <= r && g[q[r]] + s[q[r]] >= g[i] + s[i])r--;q[++r] = i;}printf("%d\n",f[n]);return 0;
}