LCIS POJ 2172 Greatest Common Increasing Subsequence

题目传送门

题意:LCIS(Longest Common Increasing Subsequence) 最长公共上升子序列

分析:a[i] != b[j]: dp[i][j] = dp[i-1][j]; a[i]==b[j]:  dp[j]=max(dp[j],dp[k]); (1<=k<j&&b[k]<b[j])  打印路径时按照b[i]来输出

收获:理解不是很深入,推荐资料: 最长公共上升子序列(LCIS)的O(n^2)算法  最长公共上升子序列的另一个O(mn)的算法

 

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std; const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;
int a[N], b[N], dp[N][N], fx[N][N], fy[N][N];
int n, m;
bool fir; void print(int x, int y, int last) { //bool fir;
if (x == 0 || y == 0) return ;
print (fx[x][y], fy[x][y], y);
if (y != last) {
if (fir) printf ("%d", b[y]), fir = false;
else printf (" %d", b[y]);
}
} void LCIS(void) {
memset (dp, 0, sizeof (dp));
memset (fx, 0, sizeof (fx));
memset (fy, 0, sizeof (fy));
int sx = 0, sy = 0;
int ret = 0, k = 0;
for (int i=1; i<=n; ++i) {
k = 0;
for (int j=1; j<=m; ++j) {
dp[i][j] = dp[i-1][j]; //以a[]为主循环,每个a[i],去找每个b[j]
fx[i][j] = i - 1; fy[i][j] = j;
if (a[i] == b[j] && dp[i][j] < dp[i][k] + 1) { //满足LCS
dp[i][j] = dp[i][k] + 1; //在1~j-1找到b[k]<a[i],满足LIS,在b[k]上更新dp
fx[i][j] = i; fy[i][j] = k;
}
else if (a[i] > b[j] && dp[i][j] > dp[i][k]) k = j; //找到最优的k
if (ret < dp[i][j]) {
ret = dp[i][j]; //更新所有dp中的最大值
sx = i, sy = j;
}
}
}
printf ("%d\n", ret);
fir = true;
print (sx, sy, -1); puts ("");
} int main(void) {
while (scanf ("%d", &n) == 1) {
for (int i=1; i<=n; ++i) scanf ("%d", &a[i]);
scanf ("%d", &m);
for (int i=1; i<=m; ++i) scanf ("%d", &b[i]);
LCIS ();
} return 0;
}

  

上一篇:最长公共上升子序列 (poj 2127) (Greatest Common Increasing Subsequence)


下一篇:LeetCode 476 Number Complement 解题报告