[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）

传送门

好难的题。。至少对我来说。

这题就是模拟从最低的平台注水，然后将最低的填满以后从最低的平台向两边扩展，每次找最近的最低的平台h，然后将水填到h高度。 栈里存的是向外扩展的时候，有时会遇到高度递减的情况，这时并不能填水，但要把这些高度都递减（即扩展时的顺序）记录进栈，然后遇到一个比比水面高的平台h时，模拟倒水，水会挨个淹没最低的平台，即需要从栈顶一个一个出战计算淹没时间，直至栈顶平台高度>h，此时h入栈。重复执行就可算出答案。

#include <cstdio> #include <iostream> #define N 100011 #define INF 1000011 #define LL long long #define min(x, y) ((x) < (y) ? (x) : (y)) int s[N]; int n, p = 1, top; LL t, sum[N], h[N], w[N], add[N], ans[N]; inline LL read() int main() for(i = 1; i <= n + 1; i++) s[++top] = i; } top = 0; l = r = s[++top] = p; for(i = 1; i <= n; i++) s[++top] = p; } for(i = 1; i <= n; i++) printf("%lld\n", ans[i]); return 0; }

　　

上一篇：[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）

下一篇：[BZOJ4993||4990] [Usaco2017 Feb]Why Did the Cow Cross the Road II（DP + 线段树）

---

单调栈