题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=760
题目的意思很是简单, 就是数据比较大。如果用一般的dp来解决的话,一定会是爆内存,爆时间的。所以,这题转化为最长单调递增子序列来求解。
将一个序列中的元素换为领一个序列中的出现相同的元素的下表。比如:
1 2 3 4 5
1 3 5 -> 1 3 5(上个序列的下标).
求最长单调递增子序列就好。。
Code:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int N = 1e5 + 4; int n, m, arr[N], brr[N], hash[N]; int ils(){ brr[1] = arr[1]; int l = 1, r = 1, mid, lenth = 1; for(int i = 2; i <= m; i ++){ l = 1, r = lenth; while(l <= r){ mid = (l + r) / 2; if(brr[mid] >= arr[i]) r = mid - 1; else l = mid + 1; } brr[l] = arr[i]; if(l > lenth) lenth ++; } return lenth; } int main(){ while(~scanf("%d %d", &n, &m)){ memset(hash, -1, sizeof(hash)); for(int i = 1; i <= n; i ++){ int x; scanf("%d", &x); if(hash[x] == -1) hash[x] = i; } bool flag = false; for(int i = 1; i <= m; i ++){ int x; scanf("%d", &x); if(hash[x] != -1) flag = true; arr[i] = hash[x]; } if(!flag) printf("0\n"); else printf("%d\n", ils()); } return 0; }