【基础练习】【线性DP】codevs1408 最长公共子序列（上升）题解

「爱情、让人受尽委屈。」 2022-08-02 06:02 151阅读 0赞

题目描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。  
小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。  
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

输入描述 Input Description

第一行N，表示A，B的长度。  
第二行，串A。  
第三行，串B。

输出描述 Output Description

输出长度

样例输入 Sample Input

4  
2 2 1 3  
2 1 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=N<=3000，A，B中的数字不超过maxlongint

看到这道题目，首先想到的是“最长公共子序列”

最长公共子序列思路是f\[i\]\[j\]表示**a的前i个和b的前j个中的最长公共子序列长度**，转移方程为：

xi = yj 时 , f\[i,j\] = f\[i-1,j-1\] + 1

xi <> yj时 , f\[i,j\] = max \{ f\[i,j-1\] , f\[i-1,j\] \}

【【但是由于本题要求的是最长公共上升子序列，上升这个要求让他必须参考末尾元素的值，因此这个方程是不对的】】

我们先放上最长公共上升子序列的方程，比较一下：

a\[i\]!=b\[j\]:   F\[i\]\[j\]=F\[i-1\]\[j\]

a\[i\]==b\[j\]:   F\[i\]\[j\]=max(F\[i-1\]\[k\])+1 1<=k<=j-1&&b\[j\]>b\[k\]

这是什么意思？这里f\[i\]\[j\]的意思发生了改变，他指的是：a的前i个和b的前j个中**以b\[j\]为结尾**的最长公共子序列

【为什么要以b\[j\]结尾？**如果不以b\[j\]结尾，那么我们求出的f\[i-1\]\[k\]也不一定是k结尾，所谓f\[i\]\[j\]只是表示“a的前i个和b的前j个中的最长公共子序列长度”**

**这样就无法保证我们选择的b\[k\]<b\[j\] 也就无法保证子序列单调递增】**

那么方程又进行了怎样的改变呢？对于方程的解释，请允许我引用@我们都爱刘汝佳的见解，原文地址在补充第三条

**“首先，在a\[i\]!=b\[j\]的时候有F\[i\]\[j\]=F\[i-1\]\[j\]。为什么呢？因为F\[i\]\[j\]是以b\[j\]为结尾的LCIS，如果F\[i\]\[j\]>0那么就说明a\[1\]..a\[i\]中必然有一个字符a\[k\]等于b\[j\]（如果F\[i\]\[j\]等于0呢？那赋值与否都没有什么影响了）。**

**因为a\[k\]!=a\[i\]，那么a\[i\]对F\[i\]\[j\]没有贡献，于是我们不考虑它照样能得出F\[i\]\[j\]的最优值。所以在a\[i\]!=b\[j\]的情况下必然有F\[i\]\[j\]=F\[i-1\]\[j\]。这一点参考LCS的处理方法。 **

**那如果a\[i\]==b\[j\]呢？首先，这个等于起码保证了长度为1的LCIS。然后我们还需要去找一个最长的且能让b\[j\]接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的F数组的第一维必然是i-1。因为i已经拿去和b\[j\]配对去了，不能用了。并且也不能是i-2，因为i-1必然比i-2更优。第二维呢？那就需要枚举b\[1\]..b\[j-1\]了，因为你不知道这里面哪个最长且哪个小于b\[j\]。**

**这里还有一个问题，可不可能不配对呢？也就是在a\[i\]==b\[j\]的情况下，需不需要考虑F\[i\]\[j\]=F\[i-1\]\[j\]的决策呢？答案是不需要。因为如果b\[j\]不和a\[i\]配对，那就是和之前的a\[1\]..a\[j-1\]配对（假设F\[i-1\]\[j\]>0，等于0不考虑），这样必然没有和a\[i\]配对优越。（为什么必然呢？因为b\[j\]和a\[i\]配对之后的转移是max(F\[i-1\]\[k\])+1，而和之前的i\`配对则是max(F\[i\`-1\]\[k\])+1。显然有F\[i\]\[j\]>F\[i\`\]\[j\],i\`>i） 于是我们得出了状态转移方程： **

**a\[i\]!=b\[j\]:   F\[i\]\[j\]=F\[i-1\]\[j\] **

**a\[i\]==b\[j\]:   F\[i\]\[j\]=max(F\[i-1\]\[k\])+1 1<=k<=j-1&&b\[j\]>b\[k\]”**

因此核心代码为：

for (int i=1;i<=n;i++)  
        {  
            for (int j=1;j<=n;j++)  
            {  
                if (a[i]==b[j])  
                {  
                    f[i][j]=1;//remember or if there's not miner before it will be 0见下方说明  
                    for (int k=j-1;k>=1;k--)//反向查找更快  
                    {  
                        if (b[k]<b[j])  
                        {  
                            f[i][j]=max(f[i][j],f[i-1][k]+1);  
                        }  
                    }  
                }  
                else   
                {  
                    f[i][j]=f[i-1][j];//make sure it ends with b[j] 在此过程中，b[j]结尾没有变  
                }  
            }  
        }

最后，只要在所有的f\[n\]\[j\]中选择最大的就可以，因为f\[n\]\[j\]一定是以b\[j\]结尾的公共上升子序列中最大的

那么放上O（n³）朴素版本代码

//codevs1408 最长公共子序列（上升） 线性DP
    //copyright by ametake
    //independently!cheer up!
    #include
       
        
    #include
        
         
    #include
         
           
    #include
          
           
    using namespace std;
    
    const int maxn=3000+10;
    int f[maxn][maxn],a[maxn],b[maxn];
    int n,l1,l2;
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    	memset(f,0,sizeof(f));
    	for (int i=1;i<=n;i++)
    	{
    		for (int j=1;j<=n;j++)
    		{
    			if (a[i]==b[j])
    			{
    				f[i][j]=1;//remember or if there's not miner before it will be 0
    				for (int k=j-1;k>=1;k--)
    				{
    					if (b[k]

`接下来是平方级的代码，详情见下面补充： //codevs1408 ×î³¤¹«¹²×ÓÐòÁÐ£¨ÉÏÉý£© ÏßÐÔDP shijianfuzadu O(n2)ÓÅ»¯°æ 
 //copyright by ametake
 //independently!cheer up!
 #include           
 #include             
 #include                
 #include                 
 using namespace std;
 
 const int maxn=3000+10;
 int f[maxn][maxn],a[maxn],b[maxn];
 int n,l1,l2;
 
 int main()
 {
 	freopen("1.txt","r",stdin);
 	scanf("%d",&n);
 	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
 	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
 	memset(f,0,sizeof(f));
 	for (int i=1;i<=n;i++)
 	{
 	    int max=0;
 		for (int j=1;j<=n;j++)
 		{	
 			f[i][j]=f[i-1][j];
 			if (a[i]>b[j]&&max                                   至于空间压缩为一位的算法，详情还是看链接吧，我在这里只放出核心代码： for(i=1;i<=n1;i++)    {         max=0;     	for(j=1;j<=n2;j++)     	{ 	    if (a[i]>b[j]&&max<f[j]) max=f[j];      	    if (a[i]==b[j]) f[j]=max+1;     	}    } 最后请让我补充几个坑点： 1.输入数据是数字而不是字符串，每个数之间都有空格，按字符串读入会挂掉，因为字符串把空格当成结尾= = 2.如果i=j，变量k循环前，要先把f[i][j]赋值为1，否则如果找不到比当前j小的k的话，f[i][j]是0，会导致wa 3.本题O（n³）算法可以胜任，但还有平方算法和一维空间算法 详情参见http://wenku.baidu.com/view/3e78f223aaea998fcc220ea0.html上文中的解释也引自这篇文章 再次感谢@我们都爱刘汝佳 同时感谢多多帮助的里奥君~ ——亦余心之所善兮，虽九死其犹未悔`

[ametake]: http://blog.csdn.net/ametake