一、最长上升子序列 LIS

题目描述

给定序列 $a$，求 $a$ 中最长上升子序列长度。

题目分析

方法1：DP。$O(n^2)$

状态表示：设 $f[i]$ 表示序列前 $i$ 个数中最长上升子序列长度。

状态计算：若 $x<i$ 且 $a[x]<a[i]$，那么 f[i]=max{f[i],f[x]+1}f[i]=max\{f[i],f[x]+1\}f[i]=max{f[i],f[x]+1}。

状态初始化：$f[i]=1$。

方法2：贪心。$O(nlogn)$

设 $f[x]$ 表示长度为 $x$ 的上升子序列的末尾的最小值，当前LIS长度为 $len$。对于序列中每个数 $a[i]$：

1. 若 $a[i]>f[len]$，那么可以构成更长的上升子序列，$f[++len]=a[i]$；
2. 否则，二分找到最小的 $l$ 使得 $f[l]>a[i]$，用 $a[i]$ 更新 $f[l]$，这使得长度为 $l$ 的上升子序列的末尾最小值更小，并且不会减少LIS长度。

贪心代码：

int n, len;
int a[MAXN], f[MAXM];int find(int x){  //二分int l = 1, r = len;while (l < r){int mid = l + r >> 1;if (f[mid] >= x) r = mid;else l = mid + 1;}return l;
}int work(){cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 2; i <= n; i ++){if (a[i] > f[len]) f[++ len] = a[i];else int l = find(a[i]), f[l] = a[i];}return len;
}

二、最长公共子序列 LCS

题目描述

给定序列 $a$ 和 $b$，求它们的最长公共子序列的长度。

题目分析

状态表示：设 $f[i,j]$ 表示 $a$ 的前 $i$ 个数与 $b$ 的前 $j$ 个数构成的LCS的长度。

状态计算：

1. f[i,j]=max{f[i−1,j],f[i,j−1]}f[i,j]=max\{f[i-1,j],f[i,j-1]\}f[i,j]=max{f[i−1,j],f[i,j−1]}；
2. 若 $a[i]=b[j]$，那么 f[i,j]=max{f[i,j],f[i−1,j−1]+1}f[i,j]=max\{f[i,j],f[i-1,j-1]+1\}f[i,j]=max{f[i,j],f[i−1,j−1]+1}。

状态初始化：无需初始化。

三、最长公共上升子序列 LCIS

题目描述：

给定序列 $a$ 和 $b$，求它们的最长公共上升子序列的长度。

题目分析

状态表示：设 $f[i,j]$ 表示 $a$ 的前 $i$ 个数与 $b$ 的前 $j$ 个数构成的，且以 $b[j]$ 结尾的LCIS的长度。注意最后答案是 max{f[n,i]},i=1,2,…,mmax\{f[n,i]\},i=1,2,…,mmax{f[n,i]},i=1,2,…,m

状态计算：

1. 若 $a[i]\ne b[j]$，那么 $f[i,j]=f[i-1,j]$；
2. 若 $a[i]=b[j]$ 且 $x<j$ 且 $b[x]<b[j]$，那么 f[i,j]=max{f[i,j],f[i,x]+1}f[i,j]=max\{f[i,j],f[i,x]+1\}f[i,j]=max{f[i,j],f[i,x]+1}。

状态初始化：无需初始化。

代码：

int n, ans;
int a[MAXN], b[MAXN], f[MAXN][MAXN];int work(){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 maxf = 1;  //用maxf存储f[i][x]+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], maxf);if(b[j] < a[i]) maxf = max(maxf, f[i - 1][j] + 1);}}for (int i = 1; i <= n; i ++)ans = max(ans, f[n][i]);return ans;
}

四、编辑距离

题目描述

设 $A$ 和 $B$ 是两个字符串。求所需最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

题目分析

状态表示：设 $f[i,j]$ 表示 $A$ 的前 $i$ 个字母转化成 $B$ 的前 $j$ 个字母所需最少的字符操作次数。

状态计算：

1. 采用操作1或2，f[i,j]=min{f[i−1,j],f[i,j−1]}+1f[i,j]=min\{f[i-1,j],f[i,j-1]\}+1f[i,j]=min{f[i−1,j],f[i,j−1]}+1；
2. 若 $A[i]=B[j]$，则无需增加操作次数，f[i,j]=min{f[i,j],f[i−1,j−1]}f[i,j]=min\{f[i,j],f[i-1,j-1]\}f[i,j]=min{f[i,j],f[i−1,j−1]}；
3. 否则采用操作3，f[i,j]=min{f[i,j],f[i−1,j−1]+1}f[i,j]=min\{f[i,j],f[i-1,j-1]+1\}f[i,j]=min{f[i,j],f[i−1,j−1]+1}。

状态初始化：$f[i,0]=f[0,i]=i$。

代码：

int n, m, f[MAXN][MAXN];
char A[MAXN], B[MAXN];int work(){cin >> A + 1 >> B + 1;n = strlen(A + 1), m = strlen(B + 1);for (int i = 0; i <= n; i ++) f[i][0] = i;for (int i = 0; i <= m; i ++) f[0][i] = i;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);}return f[n][m];
}

五、不相交区间总长

题目描述

给定 $n$ 个区间 $(x,y)$，任取一个区间或多个互不相交的区间，求取出的这些区间的总长的最大值。

题目分析

状态表示：设 $f[i]$ 表示最后一个区间的右端点 $\le i$ 的不相交区间总长最大值。

状态计算：

1. $f[i]=f[i-1]$；
2. 如果存在区间 $(a,i)$，那么 f[i]=max{f[i],f[a−1]+i−a+1}f[i]=max\{f[i],f[a-1]+i-a+1\}f[i]=max{f[i],f[a−1]+i−a+1}。

状态初始化：无需初始化。

类似于图论中的建边，我们用二维 $vector$ 按照区间右端点为关键字存储所有区间。

代码：

vector <int> m[MAXM];  //二维数组存区间
int n, maxy;  //maxy为区间右端点的最大值
int f[MAXM];int work(){scanf("%d", &n);for (int i = 1; i <= n; i ++){int x, y;scanf("%d %d", &x, &y);m[y].push_back(x);maxy = max(maxy, y); }for (int i = 1; i <= maxy; i ++){f[i] = f[i - 1];for (int j = 0; j < m[i].size(); j ++){int a = m[i][j];f[i] = max(f[i], f[a - 1] + i - a + 1);}}return f[maxy];
}