前言
感觉摆烂好久了，其实好像也没有摆烂，只是没有学新东西了，之前打算死磕网络流的，但是感觉对我们队目前来说用处不大，就算南京站真的出了，99.9999%的概率写不来，所以就去练思维了。但是好像也并没有怎么练到，被大量的作业绑架了呜呜呜QAQ。感觉dp方面还是太弱了，最后挣扎一下。
一些概念
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。
子串，串中任意个连续的字符组成的子序列称为该串的子串。
子序列定义：给定序列，从中任意地选取无限项，按照原来的顺序组成的序列称为序列的一个子序列。
最长上升子序列（LIS）
以洛谷的B3637 最长上升子序列,介绍两种不同时间复杂度的写法
解法1：朴素dp O(\(n ^ 2\))
我们不妨定义一个dp[i]用来记录以a[i]结尾的子序列的最大长度。
遍历每一个位置，对于每一个位置的dp[i]的值，我们可以从i之前的位置转移过来，举个例子
1 2 3 4 6 9
我们现在在4的位置，可以从1转移过来，也可以从2转移过来……能从在6之前，任何一个比6小的元素转移过来
不难推出状态转移方程：
$ if(a[i] > a[j]) dp[i] = max(dp[i] , dp[j] + 1); $
因为子序列最少都能有一个元素，所以将dp[i]初始化为1，那么我们不难得到下面的代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000 + 10;
int n, a[MAXN];
int dp[MAXN];
int pre[MAXN];
void output(int x) {
if (!x)return;
output(pre[x]);
cout << a[x] << " ";
//迭代输出
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
// DP
for (int i = 1; i <= n; i++) {
dp[i] = 1;
pre[i] = 0;
for (int j = 1; j < i; j++)
if (a[j] < a[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
pre[i] = j;//逐个记录前驱
}
}
int ans = dp[1], pos = 1;
for (int i = 1; i <= n; i++)
if (ans < dp[i]) {
ans = dp[i];
pos = i;
}
cout << ans << endl;
output(pos);
return 0;
}
解法2：贪心 + 二分 O(nlogn)
举个例子：
3 1 2 1 8 5 6
长度为1：3 1 2 8 5 6
长度为2：3，8 3，5 3，6 1，2 1，8 1，5 1，6
长度为3：3，5，6 1，2，8 1，2，5 1，2，6
长度为4：1，2，5，6
对于一个最长上升子序列，显然，元素越小越有利于后面元素的增长。
我们不妨维护一个low[i]数组，用来记录，长度为i的序列中最后一个元素的可能的最小值。
如果我们碰到了一个\(a[i]\)满足\(low[t] < a [i] < low[t + 1]\)，说明这个\(a[i]\)可以接在长度为t的子序列后面，而\(a[i] < q[k + 1]\)，\(a[i]\)可以作为长度为\(t + 1\)的最后一个元素的最小值。所以我们更新最小值\(low[t + 1] = a[i]\)。
易证low[i]是一个升序序列，我们可以用二分法快速找到a[i]的位置。
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n;
cin >> n;
int a[n + 1] , low[n + 1];
for(int i = 1 ; i <= n ; i ++) cin >> a[i] , low[i] = 0;
int ans = 1;
low[ans] = a[1];
for(int i = 1 ; i <= n ; i ++){
if(low[ans] < a[i]){
low[++ ans] = a[i];
}
auto t = lower_bound(low + 1 , low + 1 + ans , a[i]);//长度为ans
*t = a[i];
}
cout << ans << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while (t --){
solve();
}
return 0;
}
最长公共子序列（LIS）
解法1：朴素dp O(\(n ^ 2\))
我们不妨定义一个二维数组dp[i][j]，表示第一个序列的走到第i个位置，第二个序列走到第j个位置时公共子序列的长度。
容易得到下面的状态转移方程：
if(a[i] == b[j]){
dp[i][j] = max(dp[i][j] , dp[i - 1][j - 1] + 1);
}else{
dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
}
不难得到以下算法：
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
int a[n + 1] , b[n + 1] , dp[n + 1][n + 1];
for(int i = 0 ; i <= n ; i ++){
for(int j = 0 ; j <= n ; j ++){
dp[i][j] = 0;
}
}
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 ++){
for(int j = 1 ; j <= n ; j ++){
if(a[i] == b[j]){
dp[i][j] = max(dp[i][j] , dp[i - 1][j - 1] + 1);
}else{
dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
}
}
}
cout << dp[n][n] << "\n";
return 0;
}
解法2：map优化 O(\(nlogn\))
对于洛谷P1439 【模板】最长公共子序列，\(10^5\)的数据量在O(\(n ^ 2\))的事件复杂度下，显然超时。由于全排列的特殊性，我们可以考虑\(nlogn\)的做法：
因为两个序列都是1-n的全排列，那么两个序列元素都有唯一对应的位置。
那么我们通过一个map数组将A序列的数字在B序列中的位置表现出来。
因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入\(LCS\)——那么就可以转变成\(nlogn\)求用来记录新的位置的map数组中的LIS
不难得到下面的代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
int a[n + 1] , b[n + 1] , arr[n + 1];
map<int , int> mp;
for(int i = 1 ; i <= n ; i ++) cin >> a[i] , mp[a[i]] = i;
for(int i = 1 ; i <= n ; i ++) cin >> b[i] , arr[i] = mp[b[i]];
int low[n + 1];
int ans = 1;
memset(low , 0 , sizeof(low));
low[ans] = arr[1];
for(int i = 1; i <= n ; i ++){
if(arr[i] > low[ans]){
low[++ ans] = arr[i];
}else{
auto t = lower_bound(low + 1 , low + 1 + ans , arr[i]);
*t = arr[i];
}
}
cout << ans << "\n";
return 0;
}
后记
暂时先到这里吧，虽然好像也没有写什么东西，写的也不清楚，但还是幸苦自己了。???