寒假集训记录

1月3日：

基础子序列，用的是\(O(n^2)\)动态规划

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define inc 0xcfcfcfcf
#define N 5007
#define M 500007
#define mod 1000000007
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
struct Node
{
	int x,y,id;
}a[N];
int T=1,n,m,k;
int lst[N],f[N],cnt,num;
bool Cmp(Node x,Node y)
{
	if(x.x==y.x)
		return x.y<y.y;
	return x.x<y.x;
}
void Print(int pos)
{
	if(lst[pos]!=0)
		Print(lst[pos]);
	printf("%lld ",a[pos].id);
}
bool Solve()
{
 	//freopen("test.in","r",stdin);
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;++i)
	{
		int in1,in2;
		scanf("%lld%lld",&in1,&in2);
		if(in1>m&&in2>k)
			a[++num].x=in1,a[num].y=in2,a[num].id=i;
	}
	if(num==0)
	{
		printf("0\n");
		return 1;
	}
	sort(a+1,a+1+num,Cmp);
	for(int i=1;i<=n;++i)
	{
		int mx=0,pos=0;
		for(int j=1;j<i;++j)
			if(a[j].x<a[i].x&&a[j].y<a[i].y&&f[j]>mx)
				pos=j,mx=f[j];
		f[i]=max(f[i],mx+1);
		lst[i]=pos;
	}
	int mx=0,pos=0;
	for(int i=1;i<=n;++i)
		if(f[i]>mx)
			mx=f[i],pos=i;
	printf("%lld\n",mx);
	Print(pos);
	printf("\n");
	return true;
}
signed main()
{
	//scanf("%lld",&T);
	while(T--)
		if(!Solve())
			printf("-1\n");
	return 0;
}

/*

*/