题目来源：http://acm.nyist.cf/problem/1575

题目描述:

         今天要处决一批犯人，zz国王想要饶恕这些犯人，但作为被人民称为最严执法官的你不同意。为此你和国王争吵不休，最后在大将军LJT的提议下，两人各退一步，由国王设置处决规则。（谁让zz是国王呢）

  规则：n名罪犯，一名执法人员只处决一名罪犯，给执法人员和罪犯每人一个编号（1-n），然后zz国王会宣读他的选择（例如一号执法对员处决二号罪犯）然后按照编号从小到大站成两排，对应的执法人员处决对应的罪犯，假设执法队员手里的大刀超级长。如果两名执法队员行刑时会导致长刀碰到一起导致不能砍到罪犯，例如，那1号2号这两罪犯就会被饶恕，而被砍到的罪犯就GG了。而作为执法官的你可以选择t(t<=n)个执法队员执行任务。问最多会有多少罪犯GG。

 

输入描述:

第一行输入一个Q(Q<=100)，表示Q组输入。
每组输入第一行输入包含一个n(1 < n <= 1000)表示有n组犯人和执法人员。
每组包含两个数表示执法人员的编号和犯人的编号。
数据保证：执法人员的编码是1~n且不重复,犯人也是如此

输出描述:

每组输出一个整数表示最多能杀多少犯人。

样例输入:

复制

1
4
2 2
1 3
3 4
4 1

样例输出:

2

提示:

样例一如果执法官选择1号3号4号执行的话，因为有交叉，所以没人GG.

如果选择1号和3号的话，2号和4号就都死了（如果选2和3号的话也行也是死2人），同时也是最优的情况死两人所以输出2.

 

来源:

上传者：hclg

思路：二元组<x，y>，按x升序排序，求y的LIS即可。（比赛时候死活没想到，就在结束的那一瞬间有那么一点思路，wtcl）

参考代码：

//此处为大佬代码，等日后看懂了再来更新
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1010];
struct node
{
    int a,b;
} ans[1010];
bool cmp(node a,node b)
{
    return a.a>b.a;
}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
            cin>>ans[i].a>>ans[i].b;
        sort(ans+1,ans+n+1,cmp);
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<=n; j++)
                if(j<ans[i].b)
                    dp[j]=max(dp[j],dp[ans[i].b]+1);
        }
        cout<<dp[0]<<endl;
    }
    return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<cmath>
#include<queue>
const double pi = acos(-1);
const int N=1100;
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int q,n;
struct node
{
    int a,b;
} an[N];
int dp[N];
bool cmp(node x,node y)
{
    return x.b<y.b;
}
void LIS()
{
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<=i; j++)
        {
            if(an[i].a>an[j].a)
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        mm(dp);
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d %d",&an[i].a,&an[i].b);
        sort(an,an+n,cmp);
        LIS();
        int ans=0;
        for(int i=0; i<n; i++)
            ans=max(ans,dp[i]);
        printf("%d\n",ans+1);
    }
    return 0;
}