信息学奥赛一本通 1306：最长公共子上升序列 | OpenJudge NOI 2.6 2000:最长公共子上升序列

【题目链接】

ybt 1306：最长公共子上升序列
OpenJudge NOI 2.6 2000:最长公共子上升序列

【题目考点】

1. 动态规划：线性动规

• 最长上升子序列
• 最长公共子序列

【解题思路】

解法1：基本解法

结合求最长上升子序列和最长公共子序列的方法，完成该问题。
求X序列和Y序列的最长公共上升子序列
记$X_i$为X序列前i个元素构成的序列，$Y_j$为Y序列前j个元素构成的序列。
记X的第i个元素为x[i]，Y的第j个元素为y[j]

1. 状态定义

集合：X与Y的公共上升子序列
限制：X的前i个元素与Y的前j个元素
属性：长度
条件：最长
统计量：长度
状态定义：dp[i][j]为$X_i$与$Y_j$的以y[j]为结尾的最长公共上升子序列的长度
初始状态：
$X_0$与$Y_j$的以y[j]为结尾的最长公共上升子序列的长度为0：dp[0][j]=0
$X_i$与$Y_0$的以y[0]为结尾的最长公共上升子序列的长度为0：dp[i][0]=0

2. 状态转移方程

分割集合：$X_i$与$Y_j$的以y[j]为结尾的公共上升子序列

• 如果x[i] == y[j]，对所有满足k < j的k，如果y[k] < y[j]，那么$X_{i-1}$与$Y_j$的以y[k]为结尾的最长公共上升子序列后面添加y[j]，即为$X_i$与$Y_j$的以y[j]为结尾的最长公共上升子序列，长度为dp[i][j] = dp[i-1][k] + 1。多种情况求最大值。
• 如果x[i] != y[j]，那么以y[j]为结尾的公共上升子序列中一定不包含x[i]（如果包含的话，$X_i$的子序列的结尾就是x[i]，数值上不等于y[j]，而这个子序列是以y[j]为结尾的，产生了矛盾）。所以只能取$X_{i-1}$与$Y_j$的以y[j]为结尾的公共上升子序列，即dp[i][j] = dp[i-1][j]

3. 记录序列

设vector数组seq，seq[j]中保存当i为特定值的情况下$X_i$与$Y_j$的以y[j]为结尾的最长上升公共子序列。
i每取下一个值，seq都要清空。
在运行中，如果确定要将y[j]接在以y[k]为结尾的公共上升子序列的后面，那么seq[i]就是seq[k]后面添加y[j]形成的新的序列。

3. 输出结果

最后，如果X序列的长度为xn，Y序列的长度为yn。
那么遍历j，求$X_{xn}$与$Y_j$的以y[j]为结尾的公共上升子序列的最大值，该最大值的行下标为mxj，即dp[xn][mxj]为dp[xn][1]~dp[xn][yn]中的最大值。dp[xn][mxj]就是最长上升公共子序列的长度。
因此$X_{xn}$与$Y_{mxj}$的以y[mxj]为结尾的最长上升公共子序列为$X_{xn}$与$Y_{yn}$的最长公共上升子序列。
递推结束时，seq[j]为$X_{xn}$与$Y_j$的最长公共上升子序列。取seq[mxj]即为$X_{xn}$与$Y_{mxj}$的以y[mxj]为结尾的最长上升公共子序列，输出这个序列。

其他状态定义方法：该题当然也可以设dp[i][j]为$X_i$与$Y_j$的以x[i]为结尾的最长公共上升子序列的长度。但注意，如果这么设，在做递推时必须将i从1遍历到xn作为内层循环，将j从1遍历到yn作为外层循环。这个遍历层次次序会影响到对seq的赋值。

解法2：对解法1的优化

1. 滚动数组优化
   用一维状态dp[j]表示二维状态dp[i][j]
   在外层i从小到大遍历，内层j从小到大遍历时，
   一维状态dp[1]~dp[j-1]对应二维状态dp[i][1]~dp[i][j-1]
   一维状态dp[j]~dp[yn]对应二维状态dp[i-1][j]~dp[i-1][yn]
   如果y[k] < x[i]，当外层内层循环到k时，不会运行进x[i]==y[j]的分支，那么dp[i][k] = dp[i-1][k]。
   那么y[k] < y[j] && dp[i-1][k]+1这一句，其实可以改写为y[k] < y[j] && dp[i][k]+1（亲测可行）
   经过滚动数组优化，dp[i][k]都可以变为dp[k]，dp[i][j]=dp[i-1][j]也不用写了，dp[j]自然就是dp[i-1][j]这个值。
   替换后，递推部分代码为：

for(int i = 1; i <= xn; ++i){for(int j = 1; j <= yn; ++j){if(x[i] == y[j]){dp[j] = 1;seq[j] = vector<int>(); for(int k = 1; k < j; ++k){if(y[k] < y[j] && dp[k]+1 > dp[j]){dp[j] = dp[k]+1;seq[j] = seq[k];}}seq[j].push_back(y[j]);}}} 

2. 优化求最值
   观察解法1中的内层循环，对于每个j，都要求$1\le k\le j-1$时dp[k]的最大值。而这些最大值是有递推关系的：
   $1\le k\le j$时的dp[k]的最大值为：$1\le k\le j-1$时dp[k]的最大值与dp[j]的较大值。
   进行内层循环时，只有x[i]==y[j]时才会更新状态，因此在进行内层循环时，x[i]就是将来x[i]==y[j]时的y[j]。
   进行内层循环时，求所有满足y[j] < x[i]的dp[j]的最大值，其下标保存为mj。那么满足x[i]==y[j]的j前面的末尾元素比y[j]（或者说x[i]）小的最长公共上升子序列以mj为结尾，在它后面添加y[j]，即为$X_i$与$Y_j$的最长公共上升子序列。

【题解代码】

解法1：线性动规

• 状态定义方法1：dp[i][j]为$X_i$与$Y_j$的以y[j]为结尾的最长公共上升子序列的长度

#include<bits/stdc++.h>
using namespace std;
#define N 505
int dp[N][N];//dp[i][j]:x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列的长度
int x[N], y[N];
vector<int> seq[N];//seq[j]:当i为某确定值时，x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列 
int main()
{int xn, yn;cin >> xn;for(int i = 1; i <= xn; ++i)cin >> x[i];cin >> yn;for(int i = 1; i <= yn; ++i)cin >> y[i];for(int i = 1; i <= xn; ++i)for(int j = 1; j <= yn; ++j){if(x[i] == y[j]){dp[i][j] = 1;seq[j] = vector<int>(); for(int k = 1; k < j; ++k){if(y[k] < y[j] && dp[i-1][k]+1 > dp[i][j]){dp[i][j] = dp[i-1][k]+1;seq[j] = seq[k];}}seq[j].push_back(y[j]);}elsedp[i][j] = dp[i-1][j];}int mxj = 1;for(int j = 1;j <= yn;j++){if(dp[xn][j] > dp[xn][mxj])mxj = j;	}cout << dp[xn][mxj] << endl;for(int i = 0; i < seq[mxj].size(); ++i)cout << seq[mxj][i] << ' ';return 0;
}

• 状态定义方法2：dp[i][j]为$X_i$与$Y_j$的以x[i]为结尾的最长公共上升子序列的长度

#include<bits/stdc++.h>
using namespace std;
#define N 505
int dp[N][N];//dp[i][j]:x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列的长度
int x[N], y[N];
vector<int> seq[N];//seq[i]:当j为某确定值时，x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列 
int main()
{int xn, yn;cin >> xn;for(int i = 1; i <= xn; ++i)cin >> x[i];cin >> yn;for(int i = 1; i <= yn; ++i)cin >> y[i];for(int j = 1; j <= yn; ++j)for(int i = 1; i <= xn; ++i){if(x[i] == y[j]){dp[i][j] = 1;seq[i] = vector<int>(); for(int k = 1; k < i; ++k){if(x[k] < x[i] && dp[k][j-1]+1 > dp[i][j]){dp[i][j] = dp[k][j-1]+1;seq[i] = seq[k];}}seq[i].push_back(x[i]);}elsedp[i][j] = dp[i][j-1];}int mxi = 1;for(int i = 1;i <= xn;i++){if(dp[i][yn] > dp[mxi][yn])mxi = i;	}cout << dp[mxi][yn] << endl;for(int i = 0; i < seq[mxi].size(); ++i)cout << seq[mxi][i] << ' ';return 0;
}

解法2：对解法1的优化

#include<bits/stdc++.h>
using namespace std;
#define N 505
int dp[N];//dp[i][j]:x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列的长度
int x[N], y[N];
vector<int> seq[N];//seq[j]:当i为某确定值时，x前i个元素与y前j个元素构成的以y[j]为结尾的最长公共上升子序列  
int main()
{int xn, yn;cin >> xn;for(int i = 1; i <= xn; ++i)cin >> x[i];cin >> yn;for(int i = 1; i <= yn; ++i)cin >> y[i];for(int i = 1; i <= xn; ++i){int mj = 0;for(int j = 1; j <= yn; ++j){if (y[j] < x[i] && dp[j] > dp[mj])mj = j;if (x[i] == y[j]) {dp[j] = dp[mj] + 1;seq[j] = seq[mj];seq[j].push_back(x[i]);}}} int mxj = 1;for(int j = 1;j <= yn;j++){if(dp[j] > dp[mxj])mxj = j;	}cout << dp[mxj] << endl;for(int i = 0; i < seq[mxj].size(); ++i)cout << seq[mxj][i] << ' ';return 0;
}