面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！
問題概要
の順列
が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。
- 区間
の要素をすべて削除する (コストは
目的を達成するための最小コストを求めよ。
制約
解法 (1)：僕のやった解法
まず、操作する区間が入れ子になったり交差したりする意味はないので、操作は「残す要素を固定すると、その間隔の区間を削除していく」というものになる。
これを踏まえて次の DP をする。
dp[v]← 順列を左から見ていって、値が来たときに、値
この DP 配列をセグ木 (RMQ) に載せることで、LIS を求める DP と同じ要領で高速に更新していける。ただし DP 更新において、値 の左隣の要素も選ぶ場合については、別途遷移する。
計算量は 。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<class Monoid> struct RMQ { Monoid INF; int SIZE_R; vector<pair<Monoid,int> > dat; RMQ() {} RMQ(int n, const Monoid &inf): INF(inf) { init(n, inf); } void init(int n, const Monoid &inf) { INF = inf; SIZE_R = 1; while (SIZE_R < n) SIZE_R *= 2; dat.assign(SIZE_R * 2, pair<Monoid,int>(INF, -1)); } /* set, a is 0-indexed */ void set(int a, const Monoid &v) { dat[a + SIZE_R] = make_pair(v, a); } void build() { for (int k = SIZE_R - 1; k > 0; --k) { dat[k] = min(dat[k*2], dat[k*2+1]); } } /* update, a is 0-indexed */ void update(int a, const Monoid &v) { int k = a + SIZE_R; dat[k] = make_pair(v, a); while (k >>= 1) dat[k] = min(dat[k*2], dat[k*2+1]); } /* get {min-value, min-index}, a and b are 0-indexed */ pair<Monoid,int> get(int a, int b) { pair<Monoid,int> vleft = make_pair(INF, -1), vright = make_pair(INF, -1); for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) { if (left & 1) vleft = min(vleft, dat[left++]); if (right & 1) vright = min(dat[--right], vright); } return min(vleft, vright); } inline Monoid operator [] (int a) { return dat[a + SIZE_R].first; } /* debug */ void print() { for (int i = 0; i < SIZE_R; ++i) { Monoid val = (*this)[i]; if (val < INF) cout << val; else cout << "INF"; if (i != SIZE_R-1) cout << ","; } cout << endl; } }; const long long INF = 1LL<<60; int main() { int N; cin >> N; deque<long long> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; A.push_front(0), A.push_back(N+1), A.push_back(0); RMQ<long long> dp(N+10, INF); dp.update(0, A[1]); for (int i = 1; i <= N+1; ++i) { long long val = dp.get(0, A[i]).first + A[i-1] + A[i+1]; if (i-1 >= 0 && A[i-1] < A[i]) { chmin(val, dp.get(A[i-1], A[i-1]+1).first - A[i] + A[i+1]); } dp.update(A[i], val); } cout << dp.get(N+1, N+2).first << endl; }
解法 (2)
よくよく考えると、操作する区間は 1 個だけでよい。なぜなら、いくつかの区間について操作するくらいなら、
を選んでまとめて削除してしまった方がよいからだ。そしてそのような条件を満たす区間は単調性 (区間 A が条件を満たすならば、A を包含する区間 B も条件を満たす) を満たすので、しゃくとり法で解ける。この場合計算量は となる。
