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;
}
/*
*/
标签:num,记录,int,pos,mx,寒假,printf,集训,define
From: https://www.cnblogs.com/yexinqwq/p/17021039.html