- 题目描述：
-
在初试即将开始的最后一段日子里，laxtc重点练习了英语阅读的第二部分，他发现了一个有意思的情况。
这部分的试题最终的答案总是如下形式的：
1.A;2.C;3.D;4.E;5.F。即共有六个空格，每个空格填入一个相应的字母代表这个空格他所选择的答案，且空格中的字母不存在重复。若每个空格选择的答案都是严格递增的，则laxtc认为这个答案是和谐的，如1.A;2.C;3.D;4.E;5.F;反之，若答案中存在不递增的情况，则他认为这组答案是不和谐的，如1.A;2.C;3.B;4.E;5.F;laxtc总是希望他所选择的答案是和谐的。由于laxtc的英语并不怎么好，所以他也经常会空着一些空格，如1.A2.;3.B;4.E;5.F;此时，只要排除掉空格后的剩余部分依然是递增的，那么laxtc也认为它是和谐的。
已知共有n个空格，laxtc已经为每一个空格选择好了Ci个候选对象。laxtc想知道他最多能填写几个空格，同时保持最终答案是和谐的。
- 输入：
-
输入包含多组测试数据。每组测试数据由一个整数n（1 <= n <= 100000）开头,表示共有n个位置。
接下来共有n行数字，第i行表示laxtc为第i个空格选择的候选答案(可能会有重复的答案)。由两部分组成。第一部分为一个整数t（1 <= t <= 5），表示该空格共有t个候选答案。第二部分为t个整数，代表laxtc为该空格选择的候选答案序号（由于题数过多，这里用数字代替字母，数字在int范围内）。
- 输出：
-
输出为一个整数，代表laxtc得到的最大和谐答案组的长度，长度即填写的空格数。
- 样例输入：
-
5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5
4 1 2 3 4
4 2 3 4 5
2 2 3
2 4 5
1 1
- 样例输出：
-
5
4
思路
1. 做了20分钟 把o(n*n)的DP优化到 o(n*logn) 才发现这不就是道 LIS 变形题么, 不过仍然是 WA 到死
代码 未通过九度测试, WA 到没脾气
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std; int matrix[][];
int candi[]; int dp[]; int binary_search(int len, int x) {
int low = , high = len-; while(low <= high) {
int mid = (low+high)>>;
if(dp[mid] == x) {
return mid;
}else if(dp[mid] > x) {
high = mid - ;
}else{
low = mid + ;
}
}
return low;
}
int main() {
freopen("testcase.txt", "r", stdin);
int n;
while(scanf("%d", &n) != EOF) {
for(int i = ; i < n; i ++) {
scanf("%d", candi+i);
for(int j = ; j < candi[i]; j ++) {
scanf("%d", &matrix[i][j]);
}
} // init dp[] = matrix[][];
for(int i = ; i < candi[]; i ++) {
dp[] = min(dp[], matrix[][i]);
} int len = ; for(int i = ; i < n; i ++) {
bool added = false;
int lastNum = dp[len-];
for(int j = ; j < candi[i]; j ++) { if(!added) { // not added yet
if(matrix[i][j] > lastNum) {
dp[len++] = matrix[i][j];
lastNum = matrix[i][j];
added = ;
}else{
int pos = binary_search(len, matrix[i][j]);
dp[pos] = matrix[i][j];
}
}else {
if(matrix[i][j] >= lastNum) {
// do nothing
}else{
int pos = binary_search(len, matrix[i][j]);
dp[pos] = matrix[i][j];
}
}
}
}
printf("%d\n", len);
}
return ;
}