题解 P1295 【[TJOI2011]书架】
灵乌路空
·
·
题解
知识点: 线段树优化DP
原题面
双倍经验 P1848 [USACO12OPEN]Bookshelf G。
这边有 dalao 的神仙题解。
？我一开始为什么要写二维 DP
题意简述
给出一个长度为 n 的序列 h。
将 h 分成若干段，满足每段数字之和都不超过 m。
最小化每段的最大值之和。
1\le n\le 10^5, 1\le h_i\le 10^9
分析题意
有个非常显然的 DP ：
设 f_i 表示，已经分好 i 个数字的最小代价。
转移时枚举这一段的开头 k，将 [k,i] 作为新的一段，则有：
f_i = \min\left\{f_{k-1} +\max_{j=k}^{i}h_j\right\}\ \left(\sum_{j=k}^{i}h_j\le m\right)
暴力 DP 复杂度 O(n^2)，期望得分 30\text{pts}。
实际上能水 50\text{pts}（大雾
考虑优化。
显然，对于一个给定的 i，当 k 单增时，\max\limits_{j=k}^{i}h_j 单调不增，f_{k-1} 单调不降。
当枚举到 i 时，f_{k-1} 不会再改变，考虑 h_i 对 \max\limits_{j=k}^{i}h_j 的影响。
如图，设 i 左侧第一个满足 h > h_i 的位置为 pre_i，显然 \max\limits_{j=k}^{i}h_j(k> pre_i) 都会变为 h_i。
考虑线段树。
---
线段树维护位置 $k$ 的 $f_{k-1}$ 和 $f_{k-1}+\max\limits_{j=k}^{i} h_j$。
当枚举到一个新的 $h_i$ 时：
1. 单点修改，更新位置 $k=i$ 时的 $f_{k-1}$。
2. 根据 $h_i$ 更新区间 $[pre_{i}+1,i]$ 的 $f_{k-1}+\max\limits_{j=k+1}^{i} h_j$。
3. 二分得到 第一个不满足 $\sum\limits_{k}^{i}h_i\le m$ 的位置 $l$，则 $k\in [l+1,i]$。
4. 查询 $[l+1,i]$ 中最小的 $f_{k-1} + \max\limits_{j=k}^{i}h_j$。
复杂度 $O(n\log n)$，期望得分 $100\text{pts}$。
---
## 代码实现
```cpp
//知识点: 线段树优化DP
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define ls (now<<1)
#define rs (now<<1|1)
const int kMaxn = 1e5 + 10;
const ll kInf = 1e12 + 2077;
//=============================================================
struct SegmentTree {
int L, R;
ll f, ans, tag;
} t[kMaxn << 2];
ll n, m, h[kMaxn], w[kMaxn], sum[kMaxn], pre[kMaxn], f[kMaxn];
ll top, sta[kMaxn];
//=============================================================
inline ll read() {
ll f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Pushup(int now) {
t[now].f = std :: min(t[ls].f, t[rs].f);
t[now].ans = std :: min(t[ls].ans, t[rs].ans);
}
void Pushdown(int now) {
t[ls].ans = t[ls].f + t[now].tag;
t[rs].ans = t[rs].f + t[now].tag;
t[ls].tag = t[rs].tag = t[now].tag;
t[now].tag = kInf;
}
void Build(int now, int L, int R) {
t[now].L = L, t[now].R = R;
if (L == R) {
t[now].f = t[now].ans = t[now].tag = kInf;
return ;
}
int mid = (L + R) >> 1;
Build(ls, L, mid), Build(rs, mid + 1, R);
Pushup(now);
}
ll Query(int now, int L, int R) {
if (L <= t[now].L && t[now].R <= R) return t[now].ans;
if (t[now].tag != kInf) Pushdown(now);
int mid = (t[now].L + t[now].R) >> 1;
ll ret = kInf;
if (L <= mid) ret = std :: min(ret, Query(ls, L, R));
if (R > mid) ret = std :: min(ret, Query(rs, L, R));
return ret;
}
void Update(int now, int L, int R, ll val) {
if (L <= t[now].L && t[now].R <= R) {
t[now].ans = t[now].f + val;
t[now].tag = val;
return ;
}
if (t[now].tag != kInf) Pushdown(now);
int mid = (t[now].L + t[now].R) >> 1;
if (L <= mid) Update(ls, L, R, val);
if (R > mid) Update(rs, L, R, val);
Pushup(now);
}
void Modify(int now, int pos) {
if (t[now].L == t[now].R) {
t[now].ans = kInf;
t[now].f = f[pos - 1];
return ;
}
if (t[now].tag != kInf) Pushdown(now);
int mid = (t[now].L + t[now].R) >> 1;
if (pos <= mid) Modify(ls, pos);
else Modify(rs, pos);
Pushup(now);
}
void Prepare() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
h[i] = read();
sum[i] = sum[i - 1] + h[i];
}
sta[++ top] = 1;
for (int i = 2; i <= n; ++ i) {
while (top && h[sta[top]] < h[i]) top --;
if (top) pre[i] = sta[top];
sta[++ top] = i;
}
Build(1, 1, n);
}
//=============================================================
int main() {
Prepare();
for (int i = 1; i <= n; ++ i) {
Modify(1, i);
if (pre[i] < i) Update(1, pre[i] + 1, i, h[i]);
int l = std ::lower_bound(sum, sum + i + 1, sum[i] - m) - sum;
if (l < i) f[i] = Query(1, l + 1, i);
}
printf("%lld", f[n]);
return 0;
}
```