ZOJ 2432 Greatest Common Increasing Subsequence——dp

ZOJ 2432 Greatest Common Increasing Subsequence——dp

可以在状态转移时压缩一下路径，这样打印时就不需要判重了

注意结果为0时只输出0，这点很坑

#include #include #include #include using namespace std;typedef pair P;const int maxn = 1010;int T, n1, n2, a[maxn], b[maxn], dp[maxn][maxn];P path[maxn][maxn];void output(int i, int j) { if (dp[i][j] == 0) return; output(path[i][j].first, path[i][j].second); printf("%d ", b[j]);}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { 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(dp, 0, sizeof(dp)); memset(path, 0, sizeof(path)); for (int i = 1; i <= n1; i++) { int maxv = 0, x = 0, y = 0; for (int j = 1; j <= n2; j++) { if (a[i] == b[j]) { dp[i][j] = maxv + 1; path[i][j].first = x, path[i][j].second = y; } else { dp[i][j] = dp[i-1][j]; path[i][j] = path[i-1][j]; if (a[i] > b[j] && maxv < dp[i-1][j]) { maxv = dp[i-1][j]; x = i-1, y = j; } } } } int ans = 0, pos = 0; for (int i = 1; i <= n2; i++) { if (ans < dp[n1][i]) { ans = dp[n1][i]; pos = i; } } if (kase != 1) printf("\n"); printf("%d\n", ans); if (ans) { output(path[n1][pos].first, path[n1][pos].second); printf("%d\n", b[pos]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。