HDOJ 1423 Greatest Common Increasing Subsequence 【DP】【最长公共上升子序列】
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8768 Accepted Submission(s): 2831
Problem Description This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.
Input Each sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.
Output output print L - the length of the greatest common increasing subsequence of both sequences.
Sample Input
1
5 1 4 2 5 -12 4 -12 1 2 4
Sample Output
2
题意 找出两个序列中的最长公共上升子序列
思路 动态规划 假如 a[i] != b[j]
那么毫无疑问 a[i] 对这个LCIS是毫无贡献的 所以 dp[i][j] = dp[i - 1][j];
如果a[i] == b[j]
那么 这个最长公共上升子序列的长度至少为1 并且 找出前面可以接的最长的LCIS的长度 + 1 就可以了
AC代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <ctype.h> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e2 * 5 + 5; const int MOD = 1e9 + 7; int a[maxn], b[maxn], dp[maxn][maxn]; int main() { int t; cin >> t; while (t--) { int n, m; scanf(" %d", &n); int i, j, k; for (i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &m); for (i = 0; i < m; i++) scanf("%d", &b[i]); memset(dp, 0, sizeof(dp)); int ans = 0; for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (a[i] == b[j]) { int max_dp = 0; for (k = 0; k < j; k++) { if (dp[i][k] > max_dp && b[j] > b[k]) max_dp = dp[i][k]; } dp[i][j] += max_dp + 1; } else if (i) dp[i][j] = dp[i - 1][j]; if (dp[i][j] > ans) ans = dp[i][j]; } } cout << ans << endl; if (t) cout << endl; } }优化代码
#include <iostream> //时间优化 #include <cstdio> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <ctype.h> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e2 * 5 + 5; const int MOD = 1e9 + 7; int a[maxn], b[maxn], dp[maxn][maxn]; int main() { int t; cin >> t; while (t--) { int n, m; scanf(" %d", &n); int i, j, k; for (i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &m); for (i = 0; i < m; i++) scanf("%d", &b[i]); memset(dp, 0, sizeof(dp)); int ans = 0; int max_dp; for (i = 0; i < n; i++) { max_dp = 0; for (j = 0; j < m; j++) { if (i) dp[i][j] = dp[i - 1][j]; if (a[i] > b[j] && dp[i][j] > max_dp) max_dp = dp[i][j]; if (a[i] == b[j]) dp[i][j] = max_dp + 1; if (dp[i][j] > ans) ans = dp[i][j]; } } cout << ans << endl; if (t) cout << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433365.html
相关资源：JAVA上百实例源码以及开源项目