hdoj1423
题目分析：
两个数组a[n1] , b[n2], 求最长上升公共子序列。
我们可用一维存储 f[i] 表示 b 数组以 j 结尾， 与 a[] 数组构成的最长公共上升子序列。 对数组 d 的任意 j 位， 都枚举 a[1 ~n1]。
当a[i] == b[j] 时 ， 在1 ~ j - 1中 找出 b[k] 小于 a[ i ] 并且 d[k] 的值最大。 当 a[ i ] > b [j ] 时， 在0到j-1中，对于小于a[i]的，保存f值的最优解 （保存小于a [ i ] 并且 d[k]值最大的值所在的位置）。
#include<iostream>#include<string>#include<algorithm>#include<string.h>#include<cstring>#include<cstdio>using namespace std;int t, n1, n2, a[505], b[505], d[505];int LCIS(){for(int i = 1; i <= n1; i++){int k = 1;for(int j = 1; j <= n2; j++){if(a[i] == b[j]){d[j] = max(d[j], d[k] + 1);}else if(a[i] > b[j]){if(d[k] < d[j])k = j;}}}int mx = 0;for(int i = 1; i <= n2; i++)mx = max(mx, d[i]);return mx;}int main(){cin >> t;while(t--){memset(d, 0, sizeof(d));scanf("%d", &n1);for(int i = 1; i <= n1; i++)scanf("%d", &a[i]);scanf("%d", &n2);for(int i = 1; i <= n2; i++)scanf("%d", &b[i]);int ans = LCIS();printf("%d\n", ans);if(t != 0)printf("\n");}return 0;}
如果觉得《hdoj1423 最长上升公共子序列》对你有帮助，请点赞、收藏，并留下你的观点哦！
