BZOJ 1233 [Usaco2009Open]干草堆tower

题目地址

描述

奶牛们讨厌黑暗。 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有$N$大包的干草$(1 \leq N \leq 100000)$(从$1$到$N$编号)依靠传送带连续的传输进牛棚来。第$i$包干草有一个 宽度$W_{i}(1 \leq w_{i} \leq 10000)$。所有的干草包的厚度和高度都为$1$。

Bessie必须利用所有$N$包干草来建立起干草堆,并且按照他们进牛棚的顺序摆放。她可以相放多少包就放多少包来建立起tower的地基(当然是紧紧的放在一行中)。接下来他可以放置下一个草包放在之前一级的上方来建立新的一级。注意:每一级不能比下面的一级宽。她持续的这么放置,直到所有的草包都被安 置完成。她必须按顺序堆放,按照草包进入牛棚的顺序。说得更清楚一些:一旦她将一个草包放在第二级,她不能将接下来的草包放在地基上。
Bessie的目标是建立起最高的草包堆。

分析

这道题目很妙呀QAQ
首先肯定可以写出一个 $\Theta (n^{3})$ 的 DP,定义 $dp[i, j]$ 为当前层的干草是由第 $[i, j)$ 堆出来的,那么就有转移

$dp[i, j] = dpj - 1, k$

$sum[]为前缀和$

这道题目有一个很妙的结论:在许多干草堆之中,如果有一堆干草堆最下面的一段干草宽度最短,那么这一堆干草堆最高。

刚开始不会做,上网看了一下题解,结果全是“转自zkw” QAQ,然后看得我一脸懵逼

在善良的学长学姐的教导下好像明白了怎么推导,其实并不复杂。
有两种方案:

第一种,最下面一段干草是最短的。

第二种,最下面一段干草不是最短的那么我们经过一系列贪心的调整,能够将第二种转化成为第一种,那么转化后第二种的高度要么增加要么不变,可以感性的理解一下

所以问题就从维护当前干草堆最高变成了维护当前干草的宽度最短。
设 $f[i]$ 为由 $i \sim n$ 堆成的干草堆中最底层最短的长度。
$g[i]$ 为处于状态 $f[i]$ 时的最高高度。

那么有转移:

这样我们运用结论将 $\Theta (n^{3})$ 的 DP 成功降至 $\Theta (n^{2})$,可是 $1 \leq N \leq 100000$,$\Theta (n^{2})$ 好像也不行呢,至少也得$\Theta (nlogn)$ 或者 $\Theta (n)$ 才行呢?

然后打表观察[滑稽.jpg],把转移条件移一下项

我们发现当存在两个决策点 $j, k$ 且 $j < k , sum[k - 1] - f[k] \leq sum[j - 1] - f[j]$ 的时候选择 $k$ 显然没有选择 $j$ 优,所以我们维护 $sum[i - 1] - f[i]$ 的单调队列即可,那么时间复杂度降至 $\Theta (n)$。

如叙述不清请指出QAQ

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//2017/06/12 14:25:03
//Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
//BZOJ 1233: [Usaco2009Open]干草堆tower
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readIn(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int INF = 0x3f3f3f3f;
const int MAX = 100000 + 3;
int n;
int w[MAX];
int q[MAX], sum[MAX];
int f[MAX], g[MAX];

int main()
{
n = readIn();
for(int i = 1; i <= n; ++i) w[i] = readIn();
sum[0] = 0;
for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + w[i];

int l = 1, r = 1; q[r] = n + 1;
for(int i = n; i >= 1; --i){
while(l < r && sum[q[l + 1] - 1] - sum[i - 1] >= f[q[l + 1]]) l++;
f[i] = sum[q[l] - 1] - sum[i - 1];
g[i] = g[q[l]] + 1;
while(l < r && f[i] - sum[i - 1] < f[q[r]] - sum[q[r] - 1]) r--;
q[++r] = i;
}
printf("%d\n", g[1]);
return 0;
}
Partager