P3195 [HNOI2008] 玩具装箱
大意
这道题要求将 \(N\) 个物品分成若干连续的段，每段的代价与该段的长度和重量之和有关。求最小的费用。
思路
我们发现其符合四边形不等式，于是我们可以记录决策点，但是依旧是 \(\mathcal{O}(n ^ 2)\) 的，于是，我们发现，决策点是单调不降的，我们可以用二分去找最合适的决策点，然后用线段树维护决策点。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50000 + 10;
LL n, L, c[N], sum[N], dp[N], cover[N * 4];
void pushDown(int idx) {if (cover[idx] != -1) {cover[idx << 1] = cover[idx];cover[idx << 1 | 1] = cover[idx];cover[idx] = -1;}
}
void update(int idx, int l, int r, int ql, int qr, int val) {if (ql <= l && r <= qr) {cover[idx] = val;return;}pushDown(idx);int mid = (l + r) >> 1;if (ql <= mid) {update(idx << 1, l, mid, ql, qr, val);}if (qr > mid) {update(idx << 1 | 1, mid + 1, r, ql, qr, val);}
}
int query(int idx, int l, int r, int pos) {if (l == r) {return cover[idx] == -1 ? 0 : cover[idx];}pushDown(idx);int mid = (l + r) >> 1;if (pos <= mid) {return query(idx << 1, l, mid, pos);}return query(idx << 1 | 1, mid + 1, r, pos);
}
LL W(int l, int r) {LL x = L - ((sum[r] - sum[l]) + (LL)(r - l - 1));return x * x;
}
bool check(int mid, int nn) {int u = query(1, 1, n, mid);return(dp[nn] + W(nn, mid)) <= (dp[u] + W(u, mid));
}
int main() {cin >> n >> L;for (int i = 1; i <= n; i++) {cin >> c[i];sum[i] = sum[i - 1] + c[i];}memset(dp, 0x3f, sizeof(dp));memset(cover, -1, sizeof(cover));dp[0] = 0;for(int i = 1;i <= n;i ++){int u = query(1, 1, n, i);dp[i] = dp[u] + W(u, i);int l = i + 1, r = n;while(l < r){int mid = (l + r) >> 1;if(check(mid, i)){r = mid;}else{l = mid + 1;}}if(!check(l, i)) l ++;if(l > n) continue;update(1, 1, n, l, n, i);}cout << dp[n];return 0;
}