526互联

Educational Codeforces Round 99 (Rated for Div. 2)

发布时间 2023-11-21 16:55:32作者: gan_coder

https://codeforces.com/contest/1455

很久没有vp了，感觉思维又僵化了
A题直接看样例，直接猜是长度。
B题首先如果是
\(x=\frac{n(n+1)}{2}\)，那么就是n
否则如果\(x=\frac{n(n+1)}{2}+y\)，分成两类
y=n，ans=n+2，
y<n,我们总可以找到前面一个替换，然后恰好的到n，
选取z=n-y即可

C题感觉比B题简单啊

D题首先注意到n<=500,猜是\(O(n^3)\)dp
注意到x单调递增，那么替换的位置肯定也是递增的
\(f[i][j][k]\)表示到第i个数，且在i这个位置放j，当前的x为k，转移显然，滚动一下就行。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int inf=1<<30;
const int N=505;

//char s[N];
int n,x;
int f[N][N],a[N],g[N][N];
void cmin(int &x,int y){
	x=min(x,y);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d %d",&n,&x);
		fo(j,0,500) fo(k,0,500) f[j][k]=inf;
		fo(i,1,n) scanf("%d",&a[i]);
		
		f[a[1]][x]=0;
		if (x<a[1]) f[x][a[1]]=1;
		
		fo(i,2,n) {
			fo(j,0,500) fo(k,0,500) g[j][k]=inf;
			
			fo(j,0,500) fo(k,0,500) {
				if (a[i]>=j) cmin(g[a[i]][k], f[j][k]);
				if (a[i]>k && k>=j) cmin(g[k][a[i]], f[j][k]+1);
			}
			
			swap(f,g);
		}
		
		int ans=inf;
		fo(j,0,500) fo(k,0,500) cmin(ans, f[j][k]);
		if (ans==inf) puts("-1");
		else printf("%d\n",ans);
	}

	return 0;
}