ARC 085 F
http://arc085.contest.atcoder.jp/tasks/arc085_d
愚直な DP 解を示す。DP の値には一致した文字数を格納してあり、状態は(位置、最後に使った区間番号)としている。0 番目に番兵として区間 [-1,-1] を入れている。
int dp[100][101]; void to(int &x, int y) { x = max(x, y); } int main() { int n; cin >> n; vector<int> b(n); for (int i = 0; i < n; i++) { cin >> b[i]; } int q; cin >> q; vector<int> l(q + 1), r(q + 1); l[0] = -1; r[0] = -1; for (int i = 1; i <= q; i++) { cin >> l[i] >> r[i]; l[i]--; r[i]--; } q++; fill_n(*dp, 100 * 101, -1e9); dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < q; j++) { for (int k = 0; k < q; k++) { if (l[k] == i && r[j] <= r[k]) { to(dp[i + 1][k], dp[i][j] + b[i]); } } if (i <= r[j]) { to(dp[i + 1][j], dp[i][j] + b[i]); } else { to(dp[i + 1][j], dp[i][j] + !b[i]); } } } int ans = 0; for (int i = 0; i < q; i++) { ans = max(ans, dp[n][i]); } cout << n - ans << endl; }
区間を右端でソートすることで、DP の性質が良くなる。
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int N = 1 << 18; const int inf = 1.01e9; int dat[N * 2]; int lz[N * 2]; void apply(int k, int v) { dat[k] += v; lz[k] += v; } void push(int k) { apply(k * 2 + 0, lz[k]); apply(k * 2 + 1, lz[k]); lz[k] = 0; } void setval(int y, int v, int k = 1, int ll = 0, int rr = N) { if (rr - ll == 1) { dat[k] = v; lz[k] = 0; return; } push(k); int mm = ll + rr >> 1; if (y < mm) { setval(y, v, k * 2 + 0, ll, mm); } else { setval(y, v, k * 2 + 1, mm, rr); } dat[k] = max(dat[k * 2], dat[k * 2 + 1]); } void update(int l, int r, int v, int k = 1, int ll = 0, int rr = N) { if (rr <= l || r <= ll) return; if (l <= ll && rr <= r) { apply(k, v); return; } push(k); update(l, r, v, k * 2 + 0, ll, ll + rr >> 1); update(l, r, v, k * 2 + 1, ll + rr >> 1, rr); dat[k] = max(dat[k * 2], dat[k * 2 + 1]); } int query(int l, int r, int k = 1, int ll = 0, int rr = N) { if (rr <= l || r <= ll) return -inf; if (l <= ll && rr <= r) return dat[k]; push(k); return max(query(l, r, k * 2, ll, ll + rr >> 1), query(l, r, k * 2 + 1, ll + rr >> 1, rr)); } int main() { int n; cin >> n; vector<int> b(n); for (int i = 0; i < n; i++) { cin >> b[i]; } int q; cin >> q; vector<pair<int, int>> rl(q + 1); rl[0].first = 0; rl[0].second = 0; for (int i = 1; i <= q; i++) { cin >> rl[i].second >> rl[i].first; } sort(rl.begin(), rl.end()); q++; vector<int> l(q), r(q); vector<vector<int>> foo(n); for (int i = 0; i < q; i++) { l[i] = rl[i].second - 1; r[i] = rl[i].first - 1; if (l[i] >= 0) foo[l[i]].push_back(i); } update(1, q, -inf); int u = 0; for (int i = 0; i < n; i++) { vector<int> hoge; for (int j = 0; j < foo[i].size(); j++) { // r[t] > r[k] int t = upper_bound(r.begin(), r.end(), r[foo[i][j]]) - r.begin(); hoge.push_back(query(0, t)); } for (int j = 0; j < foo[i].size(); j++) { setval(foo[i][j], hoge[j]); } while (u < q && r[u] < i) { u++; } update(0, u, !b[i]); update(u, q, b[i]); } int ans = query(0, q); cout << n - ans << endl; }