HDU 1423 Greatest Common Increasing Subsequence——dp

HDU 1423 Greatest Common Increasing Subsequence——dp

zoj2432的简化版，但是这道题忘了说输出结果两两之间一个空格，导致pe了一发

顺便用了滚动数组优化一下

#include #include #include #include using namespace std;const int maxn = 510;const int INF = 0x3f3f3f3f;int T, n1, n2, a[maxn], b[maxn], dp[2][maxn];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)); for (int i = 1; i <= n1; i++) { int maxv = 0, p = 0; for (int j = 1; j <= n2; j++) { if (a[i] == b[j]) dp[i&1][j] = dp[!(i&1)][p] + 1; else { dp[i&1][j] = dp[!(i&1)][j]; if (a[i] > b[j] && maxv < dp[!(i&1)][j]) { maxv = dp[!(i&1)][j]; p = j; } } } } if (kase != 1) printf("\n"); int ans = 0; for (int i = 1; i <= n2; i++) ans = max(ans, dp[n1&1][i]); printf("%d\n", ans); } return 0;}

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