Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1562 Accepted Submission(s): 747
Problem Description
?? gets an sequence S with n intergers(0 < n <= 100000,0<= S[i] <= 1000000).?? has a magic so that he can change 0 to any interger(He does not need to change all 0 to the same interger).?? wants you to help him to find out the length of the longest increasing (strictly) subsequence he can get.
Input
The first line contains an interger T,denoting the number of the test cases.(T <= 10) For each case,the first line contains an interger n,which is the length of the array s. The next line contains n intergers separated by a single space, denote each number in S.
Output
For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the length of the longest increasing subsequence he can get.
Sample Input
2 7 2 0 2 1 2 0 5 6 1 2 3 3 0 0
Sample Output
Case #1: 5 Case #2: 5
Hint
In the first case,you can change the second 0 to 3.So the longest increasing subsequence is 0 1 2 3 5.
Author
FZU
Source
Recommend
wange2014 | We have carefully selected several similar problems for you:
这道题比较麻烦的是零比较难处理。如果将零拿出来，有一个bug是零不起作用（例如：1，0，2）。但是我在博客上学到一种巧妙地处理方法——把每个数减去前面零的个数，这样当遇到上面的问题时就会巧妙地避开。
#includeusing namespace std;const int MAXN = 100010;const int INF = 0x3f3f3f3f;int ar[MAXN], g[MAXN], dp[MAXN], a[MAXN];int main() { int t , cut = 0; scanf("%d", &t); while (t--) { int C0 = 0, cnt = 0; int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= n; i++) { if (a[i] == 0) C0++; else { a[i] -= C0; ar[++cnt] = a[i]; g[cnt] = INF; } } int ans = 0; for (int i = 1; i <= cnt; i++) { int k = lower_bound(g + 1, g + 1 + cnt, ar[i]) - g; dp[i] = k; g[k] = min(g[k], ar[i]); ans = max(dp[i], ans); } printf("Case #%d: %d\n", ++cut, ans + C0); } return 0;}