P1848 [USACO12OPEN]Bookshelf G（线段树优化 DP）

P1848 [USACO12OPEN]Bookshelf G

有 n n n间物品，每个物品有两个属性 W i , H i W_i, H_i Wi​,Hi​，宽度跟高度，要求把这 n n n件物品划分成若干连续的组，每组内 ∑ W i ≤ L \sum\limits W_i \leq L ∑Wi​≤L，并且要求最小化每组最大高度之和。

设 f [ i ] f[i] f[i]表示以 i i i为结尾的代价，则有：
f [ i ] = m i n ( f [ j ] + m a x j ≤ k ≤ i h [ k ] ) [ ∑ k = j i w [ i ] ≤ L ] f[i] = min(f[j] + max_{j \leq k \leq i} h[k])[\sum_{k = j} ^{i} w[i] \leq L]\\ f[i]=min(f[j]+maxj≤k≤i​h[k])[k=j∑i​w[i]≤L]
容易发现这是可以 O ( n 2 ) O(n ^ 2) O(n2)转移的，考虑如何优化，

对于某个 f [ i ] f[i] f[i]来说，以其 h [ i ] h[i] h[i]作为最大值最多可以向左拓展的点，我们可以单调栈求出来，再利用二分查找，我们可以从 i i i点向左拓展出一个点，满足 ∑ w [ i ] ≤ L \sum w[i] \leq L ∑w[i]≤L.

之后我们只要在区间上查找最小值，作为当前点的答案，更新即可，

#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

const int N = 1e6 + 10;

long long ans[N], sum[N], minn[N << 2], mans[N << 2], lazy[N << 2], f[N];

int n, m, h[N], w[N], stk[N], pre[N], top;

void push_down(int rt) {
  if (lazy[rt]) {
    mans[ls] = minn[ls] + lazy[rt];
    mans[rs] = minn[rs] + lazy[rt];
    lazy[ls] = lazy[rs] = lazy[rt];
    lazy[rt] = 0;
  }
}

void push_up(int rt) {
  minn[rt] = min(minn[ls], minn[rs]);
  mans[rt] = min(mans[ls], mans[rs]);
}

void update(int rt, int l, int r, int x) {
  if (l == r) {
    mans[rt] = 0x3f3f3f3f3f3f3f3f, minn[rt] = f[x - 1];
    return ;
  }
  push_down(rt);
  if (x <= mid) {
    update(lson, x);
  }
  else {
    update(rson, x);
  }
  push_up(rt);
}

void update(int rt, int l, int r, int L, int R, int x) {
  if (l >= L && r <= R) {
    lazy[rt] = x, mans[rt] = minn[rt] + x;
    return ;
  }
  push_down(rt);
  if (L <= mid) {
    update(lson, L, R, x);
  }
  if (R > mid) {
    update(rson, L, R, x);
  }
  push_up(rt);
}

long long query(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) {
    return mans[rt];
  }
  push_down(rt);
  long long ans = 0x3f3f3f3f3f3f3f3f;
  if (L <= mid) {
    ans = min(ans, query(lson, L, R));
  }
  if (R > mid) {
    ans = min(ans, query(rson, L, R));
  }
  return ans;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &h[i], &w[i]);
    sum[i] = sum[i - 1] + w[i];
  }
  stk[++top] = 1;
  for (int i = 2; i <= n; i++) {
    while (top && h[i] > h[stk[top]]) {
      top--;
    }
    pre[i] = stk[top], stk[++top] = i;
  }
  for (int i = 1; i <= n; i++) {
    update(1, 1, n, i);
    update(1, 1, n, pre[i] + 1, i, h[i]);
    int l = lower_bound(sum, sum + 1 + n, sum[i] - m) - sum;
    f[i] = query(1, 1, n, l + 1, i);
  }
  printf("%lld\n", f[n]);
  return 0;
}