题意
给一个长度为\(n\)的数组,数组中的数互不相同,你可以有两种操作
问最小操作多少次可以得到一个递增数列
分析
因为数组中的数很大,我们可以将其离散化然后操作,这样我们可以得到一个长度为\(n\)的排列,目的是得到一个从\(1\)到\(n\)的顺序排列
每个数最多操作一次,否则第一次可以不操作,那么我们就要找最多的不需要操作的数,如果不需要操作,则元素的位置不变,如果有这么一组不需要操作的数,我们可以发现,中间的数字是不能插进去的,所以这组数是相邻的数,那么问题就转换为找到数组内最长的相差为\(1\)的子序列,考虑用\(DP\),\(dp[i]\)表示以数字\(i\)为结尾的最长子序列长度,则转移方程为
\[dp[a[i]]=dp[a[i]-1]+1
\]
如果\(a[i]-1\)出现了,则这个数是\(a[i]-1\)的后缀,否则这个数是开头,即为\(1\)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
//#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e3 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int a[maxn], b[maxn];
int dp[maxn];
void solve() {
int n;
cin >> n;
map<int, int> mp;
rep(i, 1, n)cin >> a[i], b[i] = a[i], mp[a[i]] = i, dp[i] = 0;
sort(b + 1, b + n + 1);
rep(i, 1, n)a[mp[b[i]]] = i;
int maxx = 1;
rep(i, 1, n) {
dp[a[i]] = dp[a[i] - 1] + 1;
maxx = max(maxx, dp[a[i]]);
}
cout << n - maxx << '\n';
}
signed main() {
start;
cin >> T;
while (T--)
solve();
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章