经典dp例题

此文章总结LIS,LCS,LCIS的各种解法及其变种。
LIS: Longest Increase Sequence 最大上升子序列
LCS: Longest Common Sequence 最大相同子序列
LCIS: Longest Common Increase Sequence 上面两个都有

LIS

Longest Increase Sequence，即一个序列中数值递增的最长的一个子序列。

n^2作法

dp[i]表示以a[i]结尾的最优解，那么对于dp[i]，扫描a[1——(i-1)]，在所有的比a[i]小的数中，选出dp最大的一个，加上1就是dp[i]了。不难理解。

dp[i]=max(dp[j])+1
j<i,且a[j]<a[i]

for (int i=1;i<=n;i++){
    dp[i] = 1;
    for (int j=1;j<i;j++)    if (a[j]<a[i])
        dp[i] = max(dp[i],dp[j]+1);
}
cout << dp[n];

但这个一般用不到吧，，太简单了，

nlogn作法

在上述做法中，不难发现其实就是暴力匹配，接触了这么多算法，应该能意识到优秀的算法是很少做无用功的。。我们重新定义dp的含义：dp[i]表示长度为i的上升子序列中，结尾的数是多少。
这个定义很重要，这样一来，我们能想到dp[]是一个数值从小到大排列的数组，对于dp[i]的值，是越小越好的，是一个小小的贪心策略。遍历数组a，拿到a[i]，在dp中二分查找自己的位置，然后更新就行了。

洛谷P1439
LCS转换成LIS再求解。

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int map1[maxn],map2[maxn],dp[maxn];
int cnt=1;
int src(int l,int r,int key);
int main(){
    int n,temp;
    cin >> n;
    for (int i=1;i<=n;i++)  {cin >> temp;map1[temp]=i;}
    for (int i=1;i<=n;i++)  {cin >> temp;map2[map1[temp]]=i;}
    dp[1] = map2[1];
    for (int i=2;i<=n;i++){
        if (map2[i]>dp[cnt]){
            dp[++cnt] = map2[i];
        }else{
            dp[src(1,cnt,map2[i])] = map2[i];
        }
    }
    cout << cnt;
    return 0;
}
int src(int l,int r,int key){
    if (key<dp[l])  return l;
    if (key<dp[(l+r)/2])    return src(l+1,(l+r)/2,key);
    return src((l+r)/2+1,r,key);
}

LCS

Longest Common Sequence
两个序列的最长公共子序列。
这个貌似没有什么nlogn的作法。

n^2作法

dp[i][j]表示a序列的前i个元素和b序列的前j个元素的LIS
状态转移方程

$$
dp[i][j] = \begin{cases}dp[i-1][j-1]+1,a[i]==b[j]

max(dp[i-1][j],dp[i][j-1]),a[i]!=b[j]\end{cases}
$$

diaonima的这个插件，我迟早卸了你

for (int i=1;i<=n1;i++){
    for (int j=1;j<=n2;j++){
        if (a[i]==b[j]) dp[i][j] = dp[i-1][j-1]+1;
        else    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    }
}

LCIS