动态规划——LIS

动态规划

LIS 和LCS 问题

首先是这两个名词

LIS：Longest Increasing Subsequence，最长递增子序列
LCS：Longest Common Subsequence，最长公共子序列

然后先说一下LIS问题

lis O(n^2) 版本

放一个板子题 https://www.luogu.com.cn/problem/B3637

对于 6 5 1 4 2 7

这个的LIS 很明显就是 1 4 7 长度为三当然这个是不固定的

最简单的方法O(n^2)的算法，dp[i] 当前以i结尾能构造的LIS dp[i]=max(1, max(dp[1]~dp[i-1])+1) //[1,i-1] a[j]< a[i] 这样子的写就行了

1
void solve()
2
{
3
    int n;cin>>n;
4
    ve<int>a(n+1);
5
    for(int i=1;i<=n;i++) cin>>a[i];
6
    ve<int>dp(n+1);
7
    for(int i=1;i<=n;i++)
8
    {
9
        dp[i]=1;
10
        for(int j=1;j<=i-1;j++)
11
        {
12
            if(a[j]<a[i])
13
            {
14
                dp[i]=max(dp[i],dp[j]+1);
15
            }
16
        }
17
    }
18
    cout<<dp[n]<<'\n';
19
}

lis O(nlogn)版本

二分优化

还有一种二分的方法，跟树状数组的方法实现这个代码

二分的方法 dp[i]:代表当前长度为i的最长上升，对于当前已经来到第j个元素 [1,j] 中最小的那个能满足的元素

二分 dp 更新找到第一个大于a[j]的dp[i] （dp[i]<=a[j]) 更新 dp[i+1]=a[j];

1
void solve()
2
{
3
    int n;cin>>n;
4
    ve<int>a(n+1);
5
    for(int i=1;i<=n;i++) cin>>a[i];
6
    ve<int>dp(n+1);
7
    int len=1;
8
    dp[1]=a[1];
9
    for(int i=2;i<=n;i++)
10
    {
11
        if(a[i]>dp[len]) dp[++len]=a[i];
12
        else
13
        {
14
            int id=lower_bound(&dp[1],&dp[len],a[i])-&dp[1];
15
            if(dp[id]!=a[i]) id++;
16
            dp[id]=a[i];
17
        }
18
       // for(int j=1;j<=n;j++) cout<<dp[j]<<" \n"[j==n];
19
    }
20

21
    cout<<len<<'\n';
22
}

树状数组优化

树状数组也能处理这个问题，思路是如果当前已经遍历到了第i个元素，树状数组维护了前[1,a[i]-1] 个元素的情况所能组成的最长公共子序列。因为在 [1,a[i]-1] 这个范围下肯定会小于a[i]。

这个方法需要注意下离散化行为，因为我们维护的是权值。

1
int f[N];
2
void add(int x,int val)
3
{
4
    while(x>0&&x<N)
5
    {
6
        f[x]=max(f[x],val);
7
        x+=(x&-x);
8
    }
9
}
10
int query(int x)
11
{
12
    int ans=0;
13
    while(x)
14
    {
15
        ans=max(ans,f[x]);
16
        x-=(x&-x);
17
    }
18
    return ans;
19
}
20
void solve()
21
{
22
    int n;cin>>n;
23
    ve<int>a(n+1);
24
    for(int i=1;i<=n;i++) cin>>a[i];
25

26
    int maxa=0;
27
    for(int i=1;i<=n;i++)
28
    {
29
        int x=query(a[i]-1)+1;//长度
30
        maxa=max(maxa,x);
31
        add(a[i],x);
32
    }
33
    cout<<maxa<<"\n";
34
}

lcs 问题

最长公共子序列问题：

给出a数组，b数组，找a,b下最长公共子序列

朴素版本O(n^2)

我们可以用dp[i][j]来表示第一个串的前i位，第二个串的前j位的LCS的长度，那么我们是很容易想到状态转移方程的：

如果当前的A1[i]和A2[j]相同（即是有新的公共元素）那么 dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1);

如果不相同，即无法更新公共元素，考虑继承： dp[i][j]=max(dp[i−1][j],dp[i][j−1]

lcs O(nlogn)版本

我们可以先对a进行离散化操作。我们需要按照a的大小准则，对b操作。转换成b按照a准则下的，lis问题比如a中 [5 3] 得到5<3顺序则离散化后 5=>1 3=>2 即在b中5大小是1 3大小是2 。这个样子映射后得到的结果

这个方法需要注意重复的情况，在重复的情况需要倒序

数组无重复

1
int f[N];
2
void add(int x,int val)
3
{
4
    while(x<N)
5
    {
6
        f[x]=max(f[x],val);
7
        x+=(x&-x);
8
    }
9
}
10
int query(int x)
11
{
12
    int ans=0;
13
    while(x)
14
    {
15
        ans=max(ans,f[x]);
16
        x-=(x&-x);
17
    }
18
    return ans;
19
}
20
void solve()
21
{
22
    int n;cin>>n;
23
    ve<int>a(n+1),b(n+1);
24
    for(int i=1;i<=n;i++) cin>>a[i];
25
    for(int i=1;i<=n;i++) cin>>b[i];
26

27
    map<int,int>mp;
28
    for(int i=1;i<=n;i++) mp[a[i]]=i;
29
    int ans=0;
30
    for(int i=1;i<=n;i++)
31
    {
32
        int x=query(mp[b[i]]-1)+1;
33
        ans=max(ans,x);
34
        add(mp[b[i]],x);
35
    }
36
    cout<<ans<<'\n';
37
}

数组有重复

1
int f[N];
2
void add(int x,int val)
3
{
4
    while(x<N)
5
    {
6
        f[x]=max(f[x],val);
7
        x+=(x&-x);
8
    }
9
}
10
int query(int x)
11
{
12
    int ans=0;
13
    while(x)
14
    {
15
        ans=max(ans,f[x]);
16
        x-=(x&-x);
17
    }
18
    return ans;
19
}
20
void solve()
21
{
22
    int n;cin>>n;
23
    int m;cin>>m;
24
    ve<int>a(n+1),b(m+1);
25
    for(int i=1;i<=n;i++) cin>>a[i];
26
    for(int i=1;i<=m;i++) cin>>b[i];
27

28
    ve<ve<int>>mp(N);
29
    for(int i=1;i<=n;i++) mp[a[i]].push_back(i);
30

31

32

33
    ve<int>g;
34
    for(int i=1;i<=m;i++)
35
    {
36
        for(int j=mp[b[i]].size()-1;j>=0;j--) g.push_back(mp[b[i]][j]);
37
    }
38

39
    for(auto x:g) cout<<x<<" ";
40
    cout<<"\n-------------\n";
41

42

43
    int ans=0;
44
    for(int i=0;i<g.size();i++)
45
    {
46
        int x=query(g[i]-1)+1;
47
        ans=max(ans,x);
48
        add(g[i],x);
49
    }
50
    cout<<ans<<'\n';
51
}

二分的方法

如果对于有重复的，新数组的构造很可能会超时间复杂度那么还是二分的方法比较稳定一点