题目链接
首先我们通过最长公共子序列这道题知道了这道题的dp构造大概二维就够了，那么我们要解决的就是这里的dp[i][j]代表的意义是什么？首先我们先参考最长公共子序列里的O（n^2）朴素dp方法的dp[i][j]代表的是a数组的1i元素与b数组的1j元素之间的最长公共子序列，这里显然我们就无法保证递增性，因为我们没有保存上次的最大值，最后发现自己无法构造出一个满足情况的dp，最后只好“借鉴一下”网上大佬们的思路。
题解
我们构造一个dp[i][j]代表a的1~i号元素当以b[j]为结尾时的最长公共上升子序列，状态转移方程为如果当前a[i]!=b[j]，只有当b[j]<a[i]&&mx<dp[i-1][j],这时可以更新每层最大值mx，同时标记当前位置，方便回溯。这样做可以保证我们当a[i]==b[j]的时候，接入的公共子序列结尾是小于当前需要接入的数，即保证单调递增。
如果a[i]==b[j]则可以根据我们找到的最大值的基础上加1，同时赋值之前的保存的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<stdio.h>
int n,m,a[508],b[508],dp[508][508],per[508][508];
void opt(int x,int y){
if(!dp[x][y])return ;
else{
while(a[x]!=b[y]&&x)x--;
opt(x,per[x][y]);
printf("%d ",a[x]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
}
for(int i=1;i<=n;i++){
int mx=0,loc=0;
for(int j=1;j<=m;j++){
dp[i][j]=dp[i-1][j];
per[i][j]=j;
if(b[j]<a[i]&&mx<dp[i-1][j]){
mx=dp[i-1][j];
loc=j;
}
else if(a[i]==b[j]){
dp[i][j]=mx+1;
per[i][j]=loc;
}
}
}
int y=1;
for(int i=2;i<=m;i++){
if(dp[n][y]<dp[n][i]){
y=i;
}
}
int x=n;
printf("%d\n",dp[n][y]);
opt(x,y);
return 0;
}
|