最长公共上升子序列

已经快被这玩意搞疯了

\(\mathcal O(n^3)\) 做法

解析：\(f[i][j]\) 表示以 \(b[j]\) 结尾，字符串 \(a[i]\) 之前的公共上升子序列最大长度;

显然：\(f[i−1][j] \leq f[i][j]\)

递推：

• \(a[i]!=b[j]\)：\(f[i][j] = f[i−1][j]\)

• \(a[i]==b[j]\)：\(f[i][j] = max(f[k][j])+1,(1 \leq k < j , b[j] > b[k])\)

核心代码:

 for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++)
        {
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];
            else
            {
                int maxi=0;
                for(int k=1;k<j;k++)
                {
                    if(b[j]>b[k])
                    maxi=max(maxi,f[i-1][k]);
                }
                f[i][j]=maxi+1;
                ans=max(f[i][j],ans);
            }
        }
}

\(\mathcal O(n^2)\) 做法

我们考虑能否去掉枚举 \(k\) 的这一层循环

如果我们能够实时更新结尾元素小于 \(b[j]\) 的 \(LCIS\) 的长度的最大值，我们就能省去这一循环。

我们发现只有 \(a[i]==b[j]\) 时我们才会枚举 \(k\)。

这样我们就把问题转化成了实时更新结尾元素小于 \(a[i]\) 的 \(LCIS\) 的长度最大值。

我们可以在每次更新 \(f[i][j]\) 时判断一下是否 \(a[i]>b[j]\)。如果满足条件就说明 \(f[i][j]\) 是结尾元素小于 \(a[i]\) 的 \(LCIS\) 的长度，只需要取最大值即可。边记录，边更新，就能降低一维。

代码：

for(int i=1;i<=n;i++) {
        int maxi=0;
        for(int j=1;j<=m;j++) {
            f[i][j]=f[i-1][j];
            if(a[i]>b[j]&&f[i][maxi]<f[i][j]) maxi=j;//优化
            else if(a[i]==b[j]&&f[i][maxi]+1>f[i][j])
                f[i][j]=f[i][maxi]+1,ans2=max(ans2,f[i][j]);
        }
}

如果要输出方案，怎么办？

我们定义一个数组 \(g\) 来存储位置

for(int i=1;i<=n;i++) {
    int maxi=0;
    for(int j=1;j<=m;j++) {
		f[i][j]=f[i-1][j];
        g[i][j]=g[i-1][j];
        if(a[i]>b[j]&&f[i][maxi]<f[i][j]) maxi=j;
        else if(a[i]==b[j]&&f[i][maxi]+1>f[i][j]){
            f[i][j]=f[i][maxi]+1;
            g[i][j]=maxi;
        }
    }
}

输出时递归输出：

void Print(int p) {
	if(!p)	return ;		//边界
	Print(g[n][p]);
	printf("%d ",b[p]);	//输出序列
}

for(int i=1;i<=m;++i)
	if(f[n][i]>f[n][ans2])	//答案取最大值
		ans2=i;
cout<<f[n][ans2]<<"\n";
Print(ans2);

当然，我们还可以优化，我们发现转移的过程中 \(f[i][x]\) 只依赖 \(f[i-1][x]\)，我们就可以把空间降维。

#include<bits/stdc++.h>
#define ll long long
#define timeused ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int a[510],b[510];
int f[510],ans2;
int g[502];
void Print(int p) {
	if(!p)	return ;		//边界
	Print(g[p]);
	printf("%d ",b[p]);	//输出序列
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	for(int i=1;i<=n;i++) {
        int maxi=0;
        for(int j=1;j<=m;j++) {
            if(a[i]>b[j]&&f[maxi]<f[j]) maxi=j;
            else if(a[i]==b[j]&&f[maxi]+1>f[j]){
                f[j]=f[maxi]+1;
                g[j]=maxi;
            }
        }
	}
	for(int i=1;i<=m;++i)
		if(f[i]>f[ans2])	//答案取最大值
			ans2=i;
	cout<<f[ans2]<<"\n";
	Print(ans2);
	return 0;
}