n个位置，每个位置有两个属性s,c，要求选择3个位置i,j,k，使得si<sj<sk，并使得ci+cj+ck 最小
输入格式：
一行一个整数，n，3<=n<=3000
一行n个整数，即s
再一行n个整数，即c
动态规划 + 权值线段树优化。时间复杂度 O(nlog(n))
#include <bits/stdc++.h> using namespace std; const int inf = 1e9; const int maxn = 1e6 + 5; struct Tree { int l, r, mm; }tree[maxn]; int L[maxn], R[maxn], s[maxn], c[maxn]; int Hash[maxn], len; void pushup(int i) { tree[i].mm = min(tree[i * 2].mm, tree[i * 2 + 1].mm); } void build(int i, int l, int r) { tree[i].l = l; tree[i].r = r; tree[i].mm = inf; if (l >= r) return ; int mid = (l + r) / 2; build(i * 2, l, mid); build(i * 2 + 1, mid + 1, r); pushup(i); } void updata(int i, int p, int v) { if (tree[i].l == tree[i].r) { tree[i].mm = min(tree[i].mm, v); return ; } int mid = (tree[i].l + tree[i].r) / 2; if (mid >= p) { updata(i * 2, p, v); } else { updata(i * 2 + 1, p, v); } pushup(i); } int query(int i, int l, int r) { if (l > r) return inf; if (tree[i].l == l && tree[i].r == r) { return tree[i].mm; } int mid = (tree[i].l + tree[i].r) / 2; if (mid >= r) { return query(i * 2, l, r); } else if (l > mid) { return query(i * 2 + 1, l, r); } else { return min(query(i * 2, l, mid), query(i * 2 + 1, mid + 1, r)); } } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> s[i]; Hash[++len] = s[i]; } for (int i = 1; i <= n; i++) { cin >> c[i]; } sort (Hash + 1, Hash + len + 1); len = unique(Hash + 1, Hash + len + 1) - Hash - 1; for (int i = 1; i <= n; i++) { s[i] = lower_bound(Hash + 1, Hash + len + 1, s[i]) - Hash; } build(1, 1, len); for (int i = 1; i <= n; i++) { L[i] = query(1, 1, s[i] - 1); updata(1, s[i], c[i]); } build(1, 1, len); for (int i = n; i >= 1; i--) { R[i] = query(1, s[i] + 1, len); updata(1, s[i], c[i]); } int ans = inf; for (int i = 1; i <= n; i++) { ans = min(ans, L[i] + R[i] + c[i]); } if (ans != inf) { cout << ans << endl; } else { cout << "-1" << endl; } return 0; }
