前置知识
- 动态规划
- 树状数组（可有可无）
思路
无疑，对于一组数据，我们只需要求出一条最长的合法队列即可，即最长不上升子序列或最长不下降子序列，而 问题的时间复杂度 在这道题中显然是寄的，故我们必须将其降至 甚至 ,所以我们的第一反应就是高级数据结构优化，首当其冲的就是树状数组，成功将其降至 。
然而，在仔细阅读题目后，我们发现了一条有趣的信息，故我们可从值域入手，就可以轻松将其降到
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e4 + 10;
int n;
int f[N], g[N], a[N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
if (a[i] == 1) f[1]++, g[1] = max({g[1], g[2], g[3]}) + 1;
if (a[i] == 2) f[2] = max(f[2], f[1]) + 1, g[2] = max(g[2], g[3]) + 1;
if (a[i] == 3) f[3] = max({f[1], f[2], f[3]}) + 1, g[3]++;
// for (int j = 1; j <= 3; j++) cout << g[j] << " "; cout << endl;
}
// cout << f[1] << " " << f[2] << " " << f[3] << endl;
// cout << g[1] << " " << g[2] << " " << g[3] << endl;
cout << n - max({g[1], g[2], g[3], f[1], f[2], f[3]}) << endl;
return 0;
}