P1848 [USACO12OPEN]Bookshelf G

有$n$間物品，每個物品有兩個屬性$W_i,H_i$，寬度跟高度，要求把這$n$件物品劃分成若干連續(xù)的組，每組內(nèi)$\sum W_i\le L$，并且要求最小化每組最大高度之和。

設(shè)$f[i]$表示以$i$為結(jié)尾的代價，則有：
$$f[i]=min(f[j]+ma{x}_{j\le k\le i}h[k])[\sum _{k=j}^{i}w[i]\le L]$$
容易發(fā)現(xiàn)這是可以$O(n^2)$轉(zhuǎn)移的，考慮如何優(yōu)化，

對于某個$f[i]$來說，以其$h[i]$作為最大值最多可以向左拓展的點，我們可以單調(diào)棧求出來，再利用二分查找，我們可以從$i$點向左拓展出一個點，滿足$\sum w[i]\le L$.

之后我們只要在區(qū)間上查找最小值，作為當(dāng)前點的答案，更新即可，

#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 | 1using 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; }

總結(jié)

以上是生活随笔為你收集整理的P1848 [USACO12OPEN]Bookshelf G（线段树优化 DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。