首页 > 代码库 > HDU 1423 LICS 模板
HDU 1423 LICS 模板
http://acm.hdu.edu.cn/showproblem.php?pid=1423
4、LICS、O(lena * lenb)
设dp[i][j]表示a[]的前i项,以b[]的第j项结尾时,能匹配的最大值。
①、不匹配a[i]这个数,则是dp[i][j] = dp[i – 1][j];
②、匹配a[i]这个数,则需要a[i] == b[j] && b[j] > b[k] 推出 dp[i][j] = max(dp[i – 1][k]) + 1,
这样复杂度需要O(n3),注意到,求解dp的时候,是从dp[i][1….lenb]这样的顺序求解,而且,需要a[i] == b[j]才能算做贡献,因为要LCS嘛!那么可以记录dp[i][1…j – 1]的信息,以a[i]作为基准(因为a[i] == b[j]才能算出贡献,以那个作为基准没所谓),找出前j - 1个数中,满足LIS并且最大的那个,O(1)更新即可。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 500 + 20; int dp[maxn][maxn]; int a[maxn], b[maxn]; void work() { int lena, lenb; cin >> lena; for (int i = 1; i <= lena; ++i) { cin >> a[i]; } cin >> lenb; for (int i = 1; i <= lenb; ++i) { cin >> b[i]; } memset(dp, 0, sizeof dp); for (int i = 1; i <= lena; ++i) { for (int j = 1, cnt = 0; j <= lenb; ++j) { dp[i][j] = dp[i - 1][j]; //不要当前这个a[i] if (a[i] > b[j]) { //形成LIS cnt = max(cnt, dp[i - 1][j]); } if (a[i] == b[j]) { //形成LCS dp[i][j] = cnt + 1; } } } int ans = 0; for (int i = 1; i <= lenb; ++i) ans = max(ans, dp[lena][i]); cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; cin >> t; while (t--) { work(); if (t) printf("\n"); } return 0; }
HDU 1423 LICS 模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。