首页 > 代码库 > nyist -16
nyist -16
#include <iostream>
using namespace std;
struct node
{
int l,w;
}dp[1005];
int g[1005][1005];
int d[1005];
int k,max_v;
int f(int i)
{
if (d[i]>0) return d[i];
d[i]=1;
for (int j=0;j<k;j++)
{
if (g[i][j])
d[i]=max(d[i],f(j)+1);
}
max_v=max(max_v,d[i]);
return d[i];
}
int main()
{
int n;
cin>>n;
while (n--)
{
cin>>k;
int x,y;
for (int i=0;i<k;i++)
{
cin>>x>>y;
dp[i].l=max(x,y);
dp[i].w=min(x,y);
}
for (int i=0;i<k;i++)
{
for (int j=i+1;j<k;j++)
{
if (dp[i].l>dp[j].l && dp[i].w>dp[j].w)
{
g[j][i]=1;
g[i][j]=0;
}
else if (dp[i].l<dp[j].l && dp[i].w<dp[j].w)
{
g[j][i]=0;
g[i][j]=1;
}
else g[j][i]=g[i][j]=0;
}
d[i]=0;
}
max_v=0;
for (int i=0;i<k;i++)
f(i);
cout<<max_v<<endl;
}
return 0;
}