DP学习总结】LIS和LCS"/>
【DP学习总结】LIS和LCS
文章目录
- 最长公共子序列
- 最长上升子序列
- 最大上升子序列和
- 最长公共上升子序列
- 例题1. 最长公共子序列(模板）
- 例题2. 合唱队形
- 例题3. 友好城市
- 例题4. 导弹拦截
- m元上升子序列
最长公共子序列
- 子序列允许不连续。
定义：最长公共子序列，英文缩写为 L C S LCS LCS（Longest Common Subsequence）。其定义是，一个序列 S S S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S S S 称为已知序列的最长公共子序列。
求两个序列的 L C S LCS LCS,用 S 1 , S 2 S_1,S_2 S1,S2分别表示两个序列。那么可以定义 f [ i ] [ j ] f[i][j] f[i][j]表示 S 1 S_1 S1的 ( 1 , i ) (1,i) (1,i)和S_2 的 ( 1 , j ) 的(1,j) 的(1,j)的最长公共子序列。那么容易得到：
f [ i ] [ j ] = { f [ i − 1 ] [ j − 1 ] + 1 S 1 [ i ] = = S 2 [ j ] m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) S 1 [ i ] ! = S 2 [ j ] f[i][j]=\left\{ \begin{array}{cl} f[i - 1][j - 1] + 1 & S_1[i] == S_2[j] \\ max(f[i-1][j], f[i][j-1]) & S_1[i] != S_2[j] \\ \end{array} \right. f[i][j]={f[i−1][j−1]+1max(f[i−1][j],f[i][j−1])S1[i]==S2[j]S1[i]!=S2[j]
伪代码：
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= m; ++ j) {if(s1[i - 1] == s2[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;else f[i][j] = max(f[i - 1][j], f[i][j - 1]);}
}
时间复杂度: O ( n 2 ) \mathcal{O(n^2)} O(n2)
对于一些特殊的 L C S LCS LCS,我们有更优秀的 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)解法（结合接下来的 L I S LIS LIS)
最长上升子序列
- 子序列允许不连续。
定义：最长上升子序列 L I S LIS LIS（Longest Increasing Subsequence)，一个序列 S S S的一个子序列，这个子序列是严格（或者不严格）递增的，且长度最长。
介绍两种方法：1. O ( n 2 ) \mathcal{O(n^2)} O(n2)的DP 2. O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)的贪心
- O ( n 2 ) \mathcal{O(n^2)} O(n2)的DP
用f[i]表示 ( 1 , i ) (1, i) (1,i) 且以a[i]结尾的 L I S LIS LIS,
计算： f [ i ] = M a x ( 1 , f [ j ] + 1 ) f[i] = Max(1, f[j] + 1) f[i]=Max(1,f[j]+1) 1 ≤ j ≤ i 1 \le j \le i 1≤j≤i & a [ i ] > a [ j ] a[i] > a[j] a[i]>a[j]
伪代码：
for(int i = 1; i <= n; ++ i) {f[i] = 1;for(int j = 1; j < i; ++ j) if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);}
- O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)的贪心
参考博客以及OI-wiki
定义 f f f为当前的 L I S LIS LIS。初始化： f 1 = a 1 , l e n = 0 f_1=a_1,len=0 f1=a1,len=0
然后对于每次的 a i a_i ai，我们将其放入 f f f中：
Ⅰ：如果 f l e n < = a i f_{len} <= a_i flen<=ai, 直接加在序列后面即可. f + + l e n = a i f_{++len} = a_i f++len=ai
Ⅱ：如果 f l e n > a i f_{len} > a_i flen>ai, 那就在 f f f中找到第一个大于等于他的元素，替换掉。（如果是不是严格上升 就找到第一个大于他的元素）
伪代码：
// version 1.0
memset(f, 0x3f, sizeof f);
int mx = f[0];
for (int i = 0; i < n; ++i) {*upper_bound(f, f + n, a[i]) = a[i];// 非严格上升*lower_bound(f, f + n, a[i]) = a[i];
}
ans = 0;
while (f[ans] != mx) ++ans;
//version 2.0
vector<int> stk;
stk.push_back(a[1]);
for(int i = 2; i <= n; ++ i) {if(stk.back() <= a[i]) stk.push_back(a[i]);else *upper_bound(stk.begin(), stk.end(), a[i]) = a[i];*upper_bound(stk.begin(), stk.end(), a[i]) = a[i];// 非严格上升
}
cout << stk.size();
其实还有一种树状数组+DP的 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)(~~贪心已经 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)~~了 ）
最大上升子序列和
跟最长上升字序列类似，时间复杂度: O ( n 2 ) \mathcal{O(n^2)} O(n2)
f[i]：表示 1 ∼ i 1 \sim i 1∼i且结尾是a[i]的最大上升子序列和
计算： f [ i ] = m a x ( f [ i ] , f [ j ] + a [ i ] ) ( 1 ≤ j ≤ i ) f[i] = max(f[i], f[j] +a[i])(1\le j \le i) f[i]=max(f[i],f[j]+a[i])(1≤j≤i)
#include <bits/stdc++.h>
using namespace std;const int N = 1010;
int a[N], f[N], n;int main()
{cin >> n;int res = 0;for(int i = 1; i <= n; ++ i) cin >> a[i];for(int i = 1; i <= n; ++ i) {f[i] = a[i];for(int j = 1; j < i; ++ j)if(a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);}cout << *max_element(f + 1, f + 1 + n) << endl;
}
最长公共上升子序列
题目连接：Acwing 272
LCIS (最长公共上升子序列，Longest Common Increasing Subsequence)
与上面相似，用 f [ i ] [ j ] f[i][j] f[i][j]表示考虑a序列前 i i i个，b序列前 j j j个且以 b [ j ] b[j] b[j]结尾的所有方案中的LCIS
状态计算：
- 不考虑第 i i i个， f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j]
- 考虑第 i i i个， f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ k ] + 1 ) ( 0 ≤ k < j ) f[i][j]=max(f[i][j], f[i-1][k] + 1) ( 0\le k < j) f[i][j]=max(f[i][j],f[i−1][k]+1)(0≤k<j)
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= n; ++ j) {f[i][j] = f[i - 1][j];if(a[i] == b[j]) {for(int k = 0; k < j; ++ k) {if(b[j] > b[k])f[i][j] = max(f[i][j], f[i - 1][k] + 1);}}}}
易知上述代码时间复杂度为： O ( n 3 ) \mathcal{O(n^3)} O(n3)对于 n ≥ 1 0 3 n \ge 10^3 n≥103的范围就会的TLE了。
优化：
在选第 i i i个的时候，我们是需要 m a x ( f [ i − 1 ] [ k ] ) ( 0 ≤ k < j ) max(f[i-1][k])( 0 \le k < j) max(f[i−1][k])(0≤k<j)为上一个状态的最大值，我们可以利用一个变量存储下来，从而减少一层for
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N], n;int main()
{cin >> n;for(int i = 1; i <= n; ++ i ) cin >> a[i];for(int i = 1; i <= n; ++ i ) cin >> b[i];for(int i = 1; i <= n; ++ i) {int maxv = 1;for(int j = 1; j <= n; ++ j) {f[i][j] = f[i - 1][j];if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);if(a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);}}int res = 0;for(int i = 1; i <= n; ++ i) res = max(res, f[n][i]);cout << res << "\n";
}
时间复杂度： O ( n 2 ) \mathcal{O(n^2)} O(n2)
例题1. 最长公共子序列(模板）
P1439
题意：
给出两个序列，均为 1 ⋯ n 1 \cdots n 1⋯n的排列。求着两个序列的 L C S LCS LCS
1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105
solution：
如果利用前面 O ( n 2 ) \mathcal{O(n^2)} O(n2)的做法，显然是会TLE的。但我们换个思路去看，如果我去用第一个序列的顺序 去 映射 第二个序列的。
举个例子：
5 3 4 1 2
3 4 5 2 1
这两个序列，用第一个序列去映射第二个序列后就变成了 2 3 1 5 4。然后你就会发现，只需要求这个序列的LIS就是这两个序列的LCS了。然后利用 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)的做法去求LIS
特别的，如果出现了重复元素，是否还存在 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)做法吗？（望大佬指教）
时间复杂度： O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)
Code：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int dp[N];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;vector<int>a(n), b(n);unordered_map<int,int>mp;for(int i = 0; i < n; ++i) cin >> a[i], mp[a[i]] = i;for(int i = 0; i < n; ++i) cin >> b[i];memset(dp, 0x3f, sizeof dp);int mx = dp[n];for(int i = 0; i < n; ++i)*upper_bound(dp, dp+n, mp[b[i]]) = mp[b[i]];int ans = 0;while( dp[ans] != mx) ans ++;cout << ans << endl; return(0-0);
}
例题2. 合唱队形
Acwing 482
题意：
有 N N N个人，每个人有一个身高为 a i a_i ai，你需要找出最多的 M M M个人，使得 a 1 > ⋅ ⋅ ⋅ a i > a i + 1 < ⋅ ⋅ ⋅ < a M ( 1 ≤ i ≤ M ) a_1 > ··· a_i > a_{i+1} < ··· < a_M(1 \le i \le M) a1>⋅⋅⋅ai>ai+1<⋅⋅⋅<aM(1≤i≤M)
solution：
假设第 i i i个人为中心时的最优解。那么 a [ 1 ] ∼ a [ i ] a[1] \sim a[i] a[1]∼a[i]是一个上升严格的，并且 a [ i ] ∼ a [ M ] a[i] \sim a[M] a[i]∼a[M]s是一个严格递减的。
所有我们预处理两个数组:
f[i]:表示 1 ∼ i 1 \sim i 1∼i的最长上升子序列g[i]：表示 i ∼ n i \sim n i∼n的最长下降子序列
去枚举中心点，更新答案. A n s = m a x ( A n s , f [ i ] + g [ i ] − 1 ) ( 1 ≤ i ≤ n ) Ans = max(Ans, f[i] + g[i] - 1) (1 \le i \le n) Ans=max(Ans,f[i]+g[i]−1)(1≤i≤n)
时间复杂度： O ( n 2 ) \mathcal{O(n^2)} O(n2) (ps：若采用上诉贪心可将复杂度降为 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)
code:
#include <bits/stdc++.h>
using namespace std;const int N = 110;
int n;
int a[N], f[N], g[N];int main()
{cin >> n;for(int i = 1; i <= n; ++ i) cin >> a[i];for(int i = 1; i <= n; ++ i) {f[i] = 1;for(int j = 1; j < i; ++ j) if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);}for(int i = n; i ; -- i) {g[i] = 1;for(int j = n; j > i; -- j)if(a[i] > a[j]) g[i] = max(g[i], g[j] + 1);}int res = 0;for(int i = 1; i <= n; ++ i) res = max(res, f[i] + g[i] - 1);cout << n - res << endl;
}
例题3. 友好城市
Acwing 1012
题意：
在南岸有 N N N座城市，分别有一个友好城市在北岸并且不同城市的友好城市不同。现在给出这 N N N座城市在南岸的位置，及他友好城市的位置。求能开辟多少个航线连接这些友好城市并且航线没有相交。
solution：
如果将这 N N N所城市从小到大去排序，那么为了不让航线有相交。那他的友好城市也一定是从小到大的顺序的。也就是先双关键字排序，然后后对第二关键字求LIS
时间复杂度： O ( n 2 ) \mathcal{O(n^2)} O(n2) 同样的可将时间复杂度将为： O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)
code：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5050;
PII a[N];
int n;
int f[N];
int main()
{scanf("%d", &n);for(int i = 1; i <= n; ++ i) scanf("%d%d", &a[i].first, &a[i].second);sort(a + 1, a + 1 + n);for(int i = 1; i <= n; ++ i) {f[i] = 1;for(int j = 1; j < i; ++ j)if(a[i].second > a[j].second) f[i] = max(f[i], f[j] + 1);}cout << *max_element(f + 1, f + 1 + n) << endl;
}
例题4. 导弹拦截
题目连接：Acwing 1010
题意：
有 N N N个导弹，高度分别为 h i h_i hi，导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。问该套拦截系统最多能拦截多少个导弹，需要多少套这个拦截系统才能全部拦下来
solution:
第一问：最多能拦截多少个导弹；因为第一发炮弹能打任意高度，且接下来的不能高于前一发的高度。就是求最长不上升子序列，很显然是一个求LIS的问题（将序列反过来）。用上述的 O ( n l o g n ) \mathcal{O(nlogn)} O(nlogn)方法能够快速高效的解决
第二问：需要多少套能全部拦下来。也就是需要多少个最长不上升子序列覆盖整个序列。也就是最少的最长不上升子序列其实就是最长上升子序列
这是一个定理（qwq）：
Dilworth定理：对偏序集<A，≤>，设A中最长链的长度是n，则将A中元素分成不相交的反链，反链个数至少是n。
code：
#include <bits/stdc++.h>
using namespace std;
int main()
{vector<int> a, b;int x;while(cin >> x) a.push_back(x);int n = (int)a.size();for(int i = n - 1; i >= 0; -- i) b.push_back(a[i]);vector<int> dp(n + 10, 0x3f3f3f3f);for(int i = 0; i < n; ++ i)*upper_bound(dp.begin(), dp.end(), b[i]) = b[i];int mx = 0x3f3f3f3f; int cnt = 0;while(dp[cnt] != mx) ++ cnt;cout << cnt << endl;for(int i = 0; i <= n; ++i) dp[i] = 0x3f3f3f3f;for(int i = 0; i < n; ++i) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];cnt = 0;while(dp[cnt] != mx) ++ cnt;cout << cnt << endl;
}
另外附上大佬的贪心解法：DP+贪心解法Orz
m元上升子序列
例题：UVA12983
题意：
有 T T T组数据，每组数据给出 n ， m n，m n，m，表示给出 n n n个数，求长度为 m m m的严格上升子序列。答案对 1 e 9 + 7 1e9+7 1e9+7取模
思路：
dp + 树状数组优化
定义： d p [ i ] [ j ] dp[i][j] dp[i][j]表示长度为 i i i，并且以 a [ j ] a[j] a[j]结尾的严格上升子序列的数量
状态转移： d p [ i ] [ j ] = ∑ k < j , a [ k ] < a [ j ] d p [ i − 1 ] [ k ] dp[i][j] = \sum_{k<j,a[k] < a[j]} dp[i-1][k] dp[i][j]=∑k<j,a[k]<a[j]dp[i−1][k]
优化：由于 k < j k < j k<j，将原数组离散化。在转移时，树状数组记录 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j]的答案，那么在求 d p [ i ] [ j ] dp[i][j] dp[i][j]的时候就是加上 s u m ( a [ j ] − 1 ) sum(a[j] - 1) sum(a[j]−1)
Code：
#include <bits/stdc++.h>
#define int long long
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using LL = long long;
typedef pair<int, int> PII;
template < typename T> inline void Max(T &a, T b) { if(a < b) a = b; }
template < typename T> inline void Min(T &a, T b) { if(a > b) a = b; }
template < typename T>
struct BIT {const int n;vector<T> a;BIT(int n) : n(n) , a(n){}void add(int x, T v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] += v;}}T sum(int x) {T ans = 0;for (int i = x + 1; i > 0; i -= i & -i) {ans += a[i - 1];}return ans;}void rangeAdd(int l, int r, T v) {add(l, v);add(r, -v);}T rangeSum(int l, int r) {return sum(r) - sum(l);}
};
vector<int> alls;
int find(int x) {return lower_bound(ALL(alls), x) - alls.begin();
}
constexpr int mod = 1e9 + 7;
signed main() {cin.tie(nullptr) -> sync_with_stdio(false);int tt, cas = 1;cin >> tt;while (tt -- ) {alls.clear();int n, m;cin >> n >> m;vector<int> a(n);vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));for (int i = 0; i < n; ++ i) {cin >> a[i];alls.push_back(a[i]);}sort(ALL(alls));alls.erase(unique(ALL(alls)), alls.end());for (int i = 0; i < n; ++ i) dp[1][i] = 1, a[i] = find(a[i]);for (int i = 2; i <= m; ++ i) {BIT<int> bit(n);for (int j = 0; j < n; ++ j) {dp[i][j] = (dp[i][j] + bit.sum(a[j] - 1)) % mod;bit.add(a[j], dp[i - 1][j]);}}int ans = 0;for (int i = 0; i < n; ++ i) ans = (ans + dp[m][i]) % mod;cout << "Case " << "#" << cas ++ << ": " << ans << "\n"; }return 0;
}
更多推荐
【DP学习总结】LIS和LCS
发布评论