[AtCoder] ACL Beginner Contest D – Flat Subsequence
問題
方針
最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。
まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( i \) で終わる最長部分列の長さとします。\( d \) は \( 0 \) で初期化し、\( i – 1 \) まで \( d \) が構築できたとして、\( A_i \) について考えます。\( d(A_i) \) の更新は、
\[d(A_i) \leftarrow \max \left( d(A_i – K), d(A_i – K + 1), \cdots d(A_i + K)\right) + 1\]
となります。\( A_i – K \leq A_i \leq A_i + K \) となるので常に更新して大丈夫です。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct SegmentTree { private: int n; vector<int> node; public: SegmentTree(int N) { n = 1; while(n < N) n *= 2; node.resize(2 * n - 1, 0); } void update(int k, int x) { k += (n - 1); node[k] = x; while (k > 0) { k = (k - 1) / 2; node[k] = max(node[2 * k + 1], node[2 * k + 2]); } } int query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; if (r <= a || b <= l) return 0; if (a <= l && r <= b) return node[k]; int vl = query(a, b, 2 * k + 1, l, (l + r) / 2); int vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } }; const int MAX = 600001; int main() { int N, K; cin >> N >> K; int A[N]; for (int i = 0; i < N; i++) { cin >> A[i]; A[i] += K; } SegmentTree st(MAX); for (int i = 0; i < N; i++) { int v = st.query(A[i] - K, A[i] + K + 1); st.update(A[i], v + 1); } cout << st.query(0, MAX) << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません