今天要处决一批犯人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号3号4号执行的话因为有交叉,所以没人GG.
如果选择1号和3号的话2号和4号就都死了(洳果选2和3号的话也行也是死2人),同时也是最优的情况死两人所以输出2.
- 思路:结构体获取快排左边右边的最长上升子序列ac
-