2011-08-28 07:14:52Morris
d242. Q481: What Goes Up
d242. Q481: What Goes Up
內容 ：
Q481: What Goes Up
寫一個程式從一連串的整數序列中選出最長的嚴格遞增子序列（strictly increasing subsequence）。例如：在 1, 3, 2, 2, 4, 0 中最長的嚴格遞增子序列為 1,3, 4 或者 1, 2, 4。
輸入說明
：
只有一組測試資料。
輸入包含一連串的整數(大約500000個)，每個整數一列。請參考Sample Input。
輸出說明
：
首先輸出一列最長的嚴格遞增子序列的長度是多少。然後一列僅含有一個減號（dash character, '-'）。然後接下來為這個最長的嚴格遞增子序列的內容，每個整數一列。
如果有不止一個最長的嚴格遞增子序列，請輸出在輸入中最後出現的。例如在 1, 3, 2, 2, 4, 0 中，應該輸出 1, 2, 4 而不是 1, 3, 4。
請參考Sample Output。
範例輸入 ：
-7 10 9 2 3 8 8 1
範例輸出 ：
4 - -7 2 3 8
提示
：
出處
：
UVA 481
(管理：nanj0178)
作法 : Greedy 的 LIS
參照 http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
/**********************************************************************************/
/* Problem: d242 "Q481: What Goes Up" from UVA 481 */
/* Language: C */
/* Result: AC (36ms, 1411KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-27 19:27:34 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int A[500000], pos[500000], LIS[500000];
int BinarySearch(int l, int r, int v) {
int m, L = r;
do {
m = (l+r)/2;
if(LIS[m] >= v) {
if(m == 0)
return m;
else {
if(LIS[m-1] < v)
return m;
else
r = m-1;
}
} else {
l = m+1;
}
}while(l <= r);
return L+1;
}
int DP_LIS(int n) {
int a, b, LIS_L = -1, set, Ans = 0;
for(a = 0; a < n; a++) {
set = BinarySearch(0, LIS_L, A[a]);
LIS[set] = A[a], pos[a] = set;
if(set >= LIS_L) LIS_L = set;
}
for(a = 0; a < n; a++)
Ans = Ans > pos[a] ? Ans : pos[a];
printf("%d\n-\n", Ans+1);
LIS_L = Ans;
for(a = n-1; a >=0; a--)
if(pos[a] == Ans)
LIS[Ans] = A[a], Ans--;
for(a = 0; a <= LIS_L; a++)
printf("%d\n", LIS[a]);
}
main() {
int in = 0;
while(scanf("%d", &A[in]) == 1)
in++;
DP_LIS(in);
return 0;
}