把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1551E Fixed Point
题目大意：有一个序列，长度为n（2000），现在需要删掉其中的一些数，删掉之后原来的序列会自动缩进，你的目的是使得至少有k个数和他们的下标相等（从1开始），求最少需要删去的数的数量。

解：

这题n只有2000所以靠一个简单的dp就过去了，但如果出到2e5的话就是完全的另一道题目，可以看作是拥有多个限制条件的值型状态转移。

通过观察可以发现，如果前面有一个数a，将其移动到第a个位置需要移除的数个数为m，而它后面有个数b，移动它到第b个位置需要移除的数个数为n，且n>=m，那么实际上我在移动这个b的时候就能顺带地把a移动到合适的位置，实际上，对于我最后得到的结果，它一定是以这个形式：每个在后面的数移动到合适位置需要的个数永远大于等于前面的数，因此最后的移除个数实际上就是那个最关键的b移动到合适位置所需要的移除个数。
解决了这个问题之后就可以解决k的问题了，现在我们知道，存在着一个b（就叫它b吧），将其移动到位的过程中有一堆数被携带着移动到位了，有没有一种可能这些数的数量刚好大于等于k-1呢。
那么dp的值就确定了：dp[i]表示将i移动到位后一共有多少个数被移动到位，则dp[i]=max(dp[k])+1，这里k需要满足的条件是a[k]<a[i]且need[k]<=need[i]（need表示需要移除的数的个数），由于n只有2000，直接n2复杂度就能解决了，当dp[i]>=k时通过need[i]来更新答案的最小值。

而如果n是2e5呢，由于转移需要满足a[k]<a[i]且need[k]<=need[i]的两个完全没什么关系的条件，我们赖以生存的单调队列和权值线段树都没法派上用场……这个问题就留待解决吧。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll dp[2001],a[2001],need[2001];
int main() {
	cfast;
	int t=1;
	cin >> t;
	while (t--) {
		memset(dp, 0, sizeof(dp));
		int n, k;
		cin >> n >> k;
		int tmp = 0;
		inc(i, 1, n+1) {
			cin >> a[i];
		}
		ll mi = -1;
		inc(i, 1, n+1) {
			need[i]= i - a[i];
			if (need[i] < 0)continue;
			ll ma = 0;
			inc(j, 0, i) {
				if (need[j] <= need[i]&&a[j]<a[i]) {
					ma = max(ma, dp[j]);
				}
			}
			dp[i] = ma + 1;
			if (dp[i] >= k) {
				if (mi == -1)mi = need[i];
				else mi = min(mi, need[i]);
			}
		}
		cout << mi << endl;
	}
}
/*
2022.5.3 10:34
*/