此题为最长上升子序列和最长公共子序列的合体版本
先想一下最长公共子序列
先假设一个方案看看,假设第一个序列选择到了i,第二个序列选择到了j,我们可以画出一个方案集合
并且依据最后一个选择的不同划分为四个子集
而最长公共上升子序列的集合划分,就是在此基础之上做了进一步的合并,即:
我们将这个大方案的集合表示为f[i][j]
即:所有由第一个序列的前i个字母,和第二个序列的前j个字母,且以b[j]结尾的公共上升子序列
那么由3、4表示的不含a[i]子集就是f[i-1][j], 本题难点在于怎么算1、2这个子集
小Tip: 当没有一个状态可以很好的表示或者没办法转化的时候就继续把它分解,理论上来说一定是可以分解到能算为止的。最不济每一种方案都是一个状态(DP的核心就是能够用一个数表示并且处理一类状态,一次处理很多状态使得它的效率比较高),那么我们直接用暴搜就可以做了
所以我们继续尝试分解1、2,以倒数第二个位置不同分为,——b1,ai;——b2,ai;.....——bk,ai这些集合
而对于集合S:{—b1;—b2;—b3;…—bk}即等价于f[i-1][1],f[i-1][2]…f[i-1][k]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N];
int b[N];
int f[N][N];
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
for(int i = 1;i <= n;i ++) scanf("%d", &b[i]);
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j])//集合1、2包含a[i]的情况
{
for(int k = 0;k < j;k ++)//k从0开始代表空集
{
if(b[k] < b[j])
{
f[i][j] = max(f[i][j],f[i - 1][k] + 1);
}
}
}
}
}
int res = 0;
for(int i = 1;i <= n;i ++) res = max(res,f[n][i]);
printf("%d\n",res);
return 0;
}
优化:
for(int k = 0;k < j;k ++)
{
if(b[k] < b[j])//b[j] == a[i]所以条件等价于if(b[k] < a[i])
{
f[i][j] = max(f[i][j],f[i - 1][k] + 1);
}
}
对于这第三层循环,它的意义在于寻找f[i-1][0~j-1]的最大值,那么我们可以不需要循环一遍k,而是直接在i,j循环的时候就可以做好这件事
即将代码等价变形为:
for(int i = 1;i <= n;i ++)
{
int maxv = 1;
for(int j = 1;j <= n;j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = max(f[i][j],maxv);
if(a[i] > b[j]) maxv = max(maxv,f[i - 1][j] + 1);//等价于变形前b[k] < a[i]的情况
}
}