# C. Against the Difference [문제 링크](https://codeforces.com/contest/2136/problem/C) ## Problem Statement We define that a *block* is an array where all elements in it are equal to the length of the array. For example, - $[3, 3, 3]$, $[1]$, and $[4, 4, 4, 4]$ are *blocks*, - while $[1, 1, 1]$ and $[2, 3, 3]$ are **not**. An array is called *neat* if it can be obtained by the concatenation of an arbitrary number of *blocks* (possibly zero). Note that an empty array is always *neat*. You are given an array $a$ consisting of $n$ integers. Find the length of its longest *neat* subsequence. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \le t \le 10^4)$. The description of the test cases follows. - The first line of each test case contains an integer $n$ $(1 \le n \le 2 \cdot 10^5)$ — the length of $a$. - The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le n)$ — the elements of $a$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output a single integer — the length of the longest *neat* subsequence of $a$. ## Footnotes A sequence $c$ is a subsequence of a sequence $a$ if $c$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from arbitrary positions. ## 풀이 덱으로 각 숫자로 만들어지는 그룹의 시작과 끝을 저장한다. 모든 저장된 그룹을 끝지점을 기준으로 오름차순으로 정렬한다. dp[i]를 i번째 그룹까지 고려했을 때의 i번 위치에서의 최대 neat 부분수열의 최대 길이로 두고 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; struct line { int s, e, w; bool operator<(const line l) const { return e < l.e; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vector<deque<int>> deqs(n+1); vector<line> lines; for(int i=1;i<=n;i++) { int a; cin >> a; deqs[a].push_back(i); if(deqs[a].size() == a) { lines.push_back({deqs[a].front(), deqs[a].back(), a}); deqs[a].pop_front(); } } sort(lines.begin(), lines.end()); int last=1; vector<int> dp(n+1); for(line l : lines) { while(last+1<l.s) dp[last+1] = max(dp[last+1], dp[last]), last++; dp[l.e] = max(dp[l.e], dp[l.s-1] + l.w); } cout << *max_element(dp.begin(), dp.end()) << '\n'; } } ```