(LIS模板)AT2827 LIS
假设有序列s:
dp[i]表示以s[i]为结尾的上升子序列的最大长度.O(N2),TLE
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> using namespace std; int n, s[100010], dp[100010], ans; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", s + i); for (int i = 1; i <= n; i++) { dp[i] = 1; for (int j = 1; j < i; j++) if (s[j] < s[i]) dp[i] = max(dp[j] + 1, dp[i]); ans = max(ans, dp[i]); } printf("%d\n", ans); return 0; }AT2827 暴力
dp[i]表示长度为i的上升子序列末尾元素的最小值.O(NlogN)
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> using namespace std; int n, s[100010], dp[100010], len = 1; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", s + i); dp[i] = 0x7fffffff; } dp[1] = s[1]; for (int i = 2; i <= n; i++) if (s[i] > dp[len]) dp[++len] = s[i]; else { // 这里当然也可以用upper_bound: // int x = upper_bound(dp + 1, dp + len, s[i]) - dp; // dp[x] = min(s[i], dp[i]); int l = 0, r = len; while (l < r) { int mid = l + r >> 1; if (dp[mid] > s[i]) r = mid; else l = mid + 1; } dp[l] = min(s[i], dp[l]); } printf("%d\n", len); return 0; } AT2827 二分AT2827 二分
AcWing最长公共子序列 弱数据,序列为字母
dp[i][j]表示字符串A的i长度前缀与字符串B的j长度前缀的最长公共子序列.
#include <algorithm> #include <iostream> using namespace std; int dp[1001][1001]; char a1[2001], a2[2001]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a1[i]; for (int i = 1; i <= m; i++) cin >> a2[i]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if (a1[i] == a2[j]) dp[i][j] = dp[i - 1][j - 1] + 1; } cout << dp[n][m]; }暴力 LCS
P1439 【模板】最长公共子序列 强数据,序列为全排列.
LCS的O(NlogN)求解依赖于LIS方法.
https://www.luogu.com.cn/blog/blue/solution-p1439
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> using namespace std; int n, dp[100010], s1[100010], s2[100010], ans = 1; int rk[100010]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", s1 + i); rk[s1[i]] = i; dp[i] = 0x7FFFFFFF; } for (int i = 1; i <= n; i++) scanf("%d", s2 + i); dp[1] = rk[s2[1]]; for (int i = 2; i <= n; i++) if (rk[s2[i]] > dp[ans]) dp[++ans] = rk[s2[i]]; else { int x = upper_bound(dp + 1, dp + ans, rk[s2[i]]) - dp; dp[x] = min(rk[s2[i]], dp[i]); // int l = 0, r = ans; // while (l < r) { // int mid = l + r >> 1; // if (dp[mid] > rk[s2[i]]) // r = mid; // else // l = mid + 1; // } // dp[l] = min(rk[s2[i]], dp[l]); } printf("%d\n", ans); return 0; }P1439 二分