nyoj

nyoj

 今天要处决一批犯人，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

代码提交

•  查看讨论 发起提问
• 思路：结构体获取快排左边右边的最长上升子序列ac

• #include<iostream>
  #include<cstring>
  #include<cstdio>
  #include<algorithm>
  using namespace std;
  struct node{int x,y;
  }p[1000009];
  int dp[1000009];
  bool cmp(node a,node b)
  {if(a.x == b.x){return a.y<b.y;}return a.x<b.x;
  }
  int main()
  {int q;scanf(%d,&q);while(q--){int n;scanf(%d,&n);for(int i=0;i<n;i){scanf(%d%d,&p[i].x,&p[i].y);	}sort(p,pn,cmp);int max1 = 1;for(int i=0;i<n;i){dp[i] = 1;for(int j=0;j<i;j){if(p[i].y > p[j].y){dp[i] = max(dp[i],dp[j]1);}}max1 = max(max1,dp[i]);}printf(%d\n,max1);}return 0;
  }