题目链接：传送门
洛谷上的P4644 [USACO05DEC]Cleaning Shifts 之前没发题解太高兴了 数据结构优化dp的例题 f [ i ] f[i] f[i]表示处理到 i i i处的最小花费 拿一个线段树维护最小值用来更新 f f f数组就好了
#include <bits/stdc++.h> #define A 1000010 using namespace std; struct node { int l, r, w; friend bool operator < (const node a, const node b) { return a.r < b.r; } }tree[A], e[A]; int n, l, r, f[A]; void build(int k, int l, int r) { tree[k].l = l; tree[k].r = r; if (l == r) {tree[k].w = f[l]; return;} int m = (l + r) >> 1; build(k << 1, l, m); build(k << 1 | 1, m + 1, r); tree[k].w = min(tree[k << 1].w, tree[k << 1 | 1].w); } void change(int k, int pos, int val) { if (tree[k].l == tree[k].r) {tree[k].w = val; return;} int m = (tree[k].l + tree[k].r) >> 1; if (pos <= m) change(k << 1, pos, val); else change(k << 1 | 1, pos, val); tree[k].w = min(tree[k << 1].w, tree[k << 1 | 1].w); } int ask(int k, int l, int r) { if (tree[k].l >= l and tree[k].r <= r) return tree[k].w; int m = (tree[k].l + tree[k].r) >> 1, ans = 0x3f3f3f3f; if (l <= m) ans = min(ans, ask(k << 1, l, r)); if (r > m) ans = min(ans, ask(k << 1 | 1, l, r)); return ans; } int main(int argc, char const *argv[]) { cin >> n >> l >> r; l++; r++; if (n == 1 and l == 1 and r == 1) return puts("1"), 0; for (int i = 1; i <= n; i++) scanf("%d%d%d", &e[i].l, &e[i].r, &e[i].w), e[i].l++, e[i].r++; for (int i = l; i <= r; i++) f[i] = 0x3f3f3f3f; f[l] = 0; sort(e + 1, e + n + 1); build(1, l, r); for (int i = 1; i <= n; i++) { f[e[i].r] = min(f[e[i].r], ask(1, e[i].l - 1, e[i].r) + e[i].w); change(1, e[i].r, f[e[i].r]); } if (f[r] == 0x3f3f3f3f) puts("-1"); else cout << f[r] << endl; }