本文共 853 字，大约阅读时间需要 2 分钟。
转换最长公共子问题转化为最长子问题，那么增加nlogn的方式来解决这个问题最长增加子。在解决方案的整个主题的出。
#include #include #include using namespace std;typedef int NUMBER;typedef int INDEX;map m;#define INF 0x7fffffffint arr[62505];int g[63505];void func(int len){ static int case_n = 1; int i, p, max_len; for(i=1; i<=len; i++) g[i] = INF; max_len = -1; for(i=1; i<=len; i++){ p = lower_bound(g+1, g+i, arr[i])-g; if(max_len < p) max_len = p; g[p] = arr[i]; } printf("Case %d: %d\n", case_n++, max_len);}int main(void){ int t, n, p, q, i, num; //freopen("input.dat", "r", stdin); scanf("%d", &t); while(t--){ scanf("%d %d %d", &n, &p, &q); for(i=1; i<=p+1; i++){ scanf("%d", &num); m[num] = i; } for(i=1; i<=q+1; i++){ scanf("%d", &num); arr[i] = m[num]; } func(q+1); } return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。