zoj2431 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2432
hdoj 1423 http://acm.hdu.edu.cn/showproblem.php?pid=1423
题意:
一看题目题意就很明显了, 两个数组a,b,求出两个数组公共的最长的上升子序列(可以不是连续的子序列)。
分析:
如果做过 [ 最长公共子序列 ]( http://blog.csdn.net/wangdan11111/article/details/41321277 )应该更容易明白点。
定义状态d [ i ] [ j ]表示以a数组的前i个元素,b数组的前j个元素并且以b[j]为结尾的LCIS的长度。
首先:a [ i ] != b[j]时, d[i]
举个例子
a={1, 4, 2, 5, -12} b ={5, -12, 1, 2, 4, 5}
5 | -12 | 1 | 2 | 4 | 5 | |
1 | 0 | 0 | 1 | 0 | 0 | 0 |
4 | 0 | 0 | 1 | 0 | 2 | 0 |
2 | 0 | 0 | 1 | 2 | 2 | 0 |
5 | 1 | 0 | 1 | 2 | 2 | 3 |
-12 | 1 | 1 | 1 | 2 | 2 | 3 |
if(a[i] == b[j])
d[i][j] = mx + 1;
else if(a[i] > b[j] && mx < d[i-1][j])
mx = d[i-1][j];
//只有当a[i] > b[j]时,才更新mx, 保证了所求序列是上升的。
仔细看表格会发现: 若d[i][j] > 0 的话,那么在数组a前i个元素中一定存在a[k]( 1 <= k <= i)等于b[j]. 否则说明前i个a元素中没有与b[j]相同的元素。
zoj2432
#include<iostream> #include<cstdio> #include<string.h> #include<cstring> #include<math.h> using namespace std; const int N = 505; int n1, n2, t, mx, sum; int a[N], b[N], d[N][N], pi[N][N], pj[N][N]; void dp() { for(int i = 1; i <= n1; i++) { int mx = 0, x = 0, y = 0; for(int j = 1; j <= n2; j++) { d[i][j] = d[i-1][j]; pi[i][j] = i-1; pj[i][j] = j; if(a[i] > b[j] && mx < d[i-1][j]) { mx = d[i-1][j]; x = i-1; y = j; } else if(a[i] == b[j]) { d[i][j] = mx + 1; pi[i][j] = x; pj[i][j] = y; } } } } void ac(int x, int y) { if(d[x][y] == 0) return; int fx = pi[x][y]; int fy = pj[x][y]; ac(fx, fy); if(d[x][y] != d[fx][fy] && y != 0) { printf("%d", b[y]); sum++; if(sum < mx) printf(" "); else printf("/n"); } } int main() { cin >> t; while(t--) { 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]); memset(d, 0, sizeof(d)); memset(pi, -1, sizeof(pi)); memset(pj, -1, sizeof(pj)); dp(); mx = 0; int flag = 0; for(int i = 1; i <= n2; i++) { if(d[n1][i] > mx) { mx = d[n1][i]; flag = i; } } printf("%d/n", mx); for(int i = 1; i <= n1; i++) { for(int j = 1; j <= n2; j++) printf("%d ", d[i][j]); printf("/n"); } sum = 0; if(mx > 0) ac(n1, flag); if(t) printf("/n"); } return 0; }View Code
hdoj1423
#include<iostream> #include<cstdio> #include<string.h> #include<cstring> #include<math.h> using namespace std; int n1, n2, t, k; int a[505], b[505], d[505][505]; int dp() { int mx; for(int i = 1; i <= n1; i++) { mx = 0; for(int j = 1; j <= n2; j++) { d[i][j] = d[i-1][j]; if(a[i] > b[j] && mx < d[i-1][j]) mx = d[i-1][j]; else if(a[i] == b[j]) d[i][j] = mx + 1; } } mx = 0; for(int i = 1; i <= n2; i++) { if(d[n1][i] > mx) mx = d[n1][i]; } return mx; } int main() { cin >> t; while(t--) { 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]); memset(d, 0, sizeof(d)); int ans = dp(); printf("%d/n", ans); if(t) printf("/n"); } return 0; }View Code