1575

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 
 4
4 1

样例输出:

2

提示:

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

如果选择1号和号的话，2号和4号就都死了（如果选2和号的话也行也是死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(ans1,ansn1,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>
ct double pi = acos(-1);
ct int =1100;
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int q,n;
struct node
{int a,b;
} an[];
int dp[];
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,ann,cmp);LIS();int ans=0;for(int i=0; i<n; i)ans=max(ans,dp[i]);printf(%d\n,ans1);}return 0;
}