算法学习：LIS与LCS

哦哟筷子 · 2019-08-11 09:46:34 · 题解

1.LIS

• 状态定义：f[i] 表示第i个数(第i个数记为a_i)结尾的LIS的长度
• 初状态：f[0] = 0
• 末状态：max \{ f[i] \} (1 \le i \le n)
• 状态转移方程： f[i] = max \{ f[j]\} +1 (0 \le j < i,a_j < a_i)

（是不是非常好理解呢）

初状态是显然的；末状态是任意数都可以作为结尾，只比较长度；转移方程每一个状态是从所有前一个状态中最大值加上a_i

代码咕咕咕（大雾

显然，这样的复杂度是不够优秀的，所以就有了一部分的优化。我们观察状态转移方程，发现需要我们计算前i - 1项的最大值，而这可以用一些奇奇怪怪的数据结构来维护，这里就不多介绍了 （我才不会说是我不会）

然而事实上还有更优的做法，用二分（lowerbound）+贪心的做法 显然对于同样位置，结尾数字越小，结果越优。 首先我们维护一个b数组，对于每一个a_i 我们判断如果a_i大于当前的数组尾端的数，就把a_i加到数组末端，如果小于，就用a_i替换当前b数组中第一个比a_i大的数。

这个做法显然如果暴力查找，复杂度仍然是O(n^2) 但是b数组是一个单调递增的，我们可以用二分查找或者STL库中的lowerbound(这个同样自行百度233) 复杂度可以降低到O(nlogn)

但是如果有兴趣自行举例，可以发现b数组中存的并不是我们求的LIS,只是可以确保自学列的长度相同 （正确性自行证明吧）

咕咕咕的代码如下

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int N;
int a[MAXN],b[MAXN];
int p;

int main() {
    scanf("%d",&N);
    for (register int i = 1; i <= N; i++) {
        scanf("%d",&a[i]);
    }
    for (register int i = 1; i <= N; i++) {
        if (a[i] > b[p]) {
            b[++p] = a[i];
        }
        else {
            b[lower_bound(b + 1,b + p + 1,a[i]) - b] = a[i];
        }
    }
    printf("%d",p);
    return 0;
}

例题（模板）

2.LCS

咕咕咕咕咕咕咕咕咕咕咕

• 状态定义：f[i][j] 表示a_1到a_i和b_1到b_j的LCS
• 初状态：f[i][0]=f[0][j] =0(0 \le i \le |a|,0 \le j \le |b|) 其中|a|,|b|表示a,b数组的长度
• 末状态：f[|a|][|b|]
• 状态转移方程：f[i][j] = max \{ f[i][j - 1],f[i -1][j],f[i-1][j-1] +1(a_i = b_j)\}

同样非常好理解吧QWQ 注意一下a_i=b_j只是第三个选项的条件，其他的真的挺好理解的哇。

正如刚才所说O(n^2)的复杂度是不够优秀的，而更优秀的做法就要联系当我们之前所用的LIS了 我们举个例子

3 1 2 4 5
1 4 5 2 3

我们对着上面一行对下面进行离散化（不会的去面壁百度） 得到

2 4 5 3 1

也就是每一位存的是第二行这一位在第一行对应的位置，然后我们通过我们某种巧妙的玄学方法看出来，这里相当于求一个LIS嘛（这里感性理解一下，因为我不会证明，反正OI不需要证明） 然后我们做一遍LIS就做完啦！！

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int N;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int f[MAXN],p = 0;

int main() {
    scanf("%d",&N);
    for (register int i = 1; i <= N; i++) {
        scanf("%d",&a[i]);
    }
    for (register int i = 1; i <= N; i++) {
        scanf("%d",&b[i]);
    }
    for (register int i = 1; i <= N; i++) {
        c[a[i]] = i;
    }
    for (register int i = 1; i <= N; i++) {
        d[i] = c[b[i]];
    }
    for (register int i = 1; i <= N; i++) {
        if (d[i] > f[p]) {
            f[++p] = d[i];
        }
        else{
            f[lower_bound(f + 1,f + p + 1,d[i]) - f] = d[i];
        }
    }
    printf("%d",p);
    return 0;
}

例题模板

完结撒花！！