题目链接:
https://www.luogu.org/problemnew/show/CF10D
方法一
分析
$LCS$和$LIS$已经成烂大街的知识了,可是当这两个合并起来成为$LCIS$,解决的方式方法也多了起来.
首先有种最朴素的$O(N^4)$方法,$f[i][j]$表示A串第$i$个字母和B串第$j$个字母结尾的状态中$LCIS$的长度,那么
那么如果$a[i]==b[j]$,$f[i][j]=max_{0<=k<j,b[k]<a[i]} (f[i-1][k])+1$
否则$f[i][j]=f[i-1][j]$
但是这种方法怎么打印方案呢?我们用$path[j][len[j]]$表示以$j$结尾的$LCIS$方案,$len[j]$指的是以$j$结尾的$LCIS$长度
这样我们从$k$更新到$j$时,首先将$path[k][len[k]]$全部复制到$path[j][len[j]]$;
然后$len[j]=len[k]+1,path[j][len[j]]=b[j]$
跑时950+ms
代码
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <vector>
#define ll long long
#define ri register int
using std::max;
using std::min;
using std::swap;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=505;
const int inf=0x7fffffff;
int n,m,a[maxn],b[maxn],f[maxn][maxn],len[maxn];
int path[maxn][maxn];
void print(int x){
for(ri i=1;i<=len[x];i++)printf("%d ",path[x][i]);
puts("");
return ;
}
int main(){
int x,y,z;
int ans=-inf,ed=0;
read(n);
for(ri i=1;i<=n;i++){read(a[i]);}
read(m);
for(ri i=1;i<=m;i++){read(b[i]);}
a[0]=b[0]=-inf;
for(ri i=1;i<=n;i++){
for(ri j=1;j<=m;j++){
if(a[i]==b[j]){
for(ri k=0;k<j;k++){
if(b[k]<a[i]){
if(f[i][j]<f[i-1][k]+1){
f[i][j]=f[i-1][k]+1;
len[j]=len[k]+1;
for(ri p=1;p<=len[k];p++)path[j][p]=path[k][p];
}
}
}
}
else f[i][j]=f[i-1][j];
path[j][len[j]]=b[j];
if(ans<f[i][j]){
ans=f[i][j];
ed=j;
}
}
}
printf("%d\n",ans);
print(ed);
return 0;
}
|
方法二
我们考虑递推时的决策集合,$f[i][j]$都是由$f[i]k$递推得到,那么我们如果在从$f[i][0]$递推到$f[i][j]$时我们已经记录下所有$f[i][k]$的最大值设为$val$,直接将$f[i][j]$设为$max(f[i][j],val+1)$就好了，打印路径的方法跟方法一类似
这样时间复杂度能少个$N$
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <queue>
#include <algorithm>
#define ll long long
#define ri register int
#define ull unsigned long long
using std::min;
using std::max;
using std::swap;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=505;
const int inf=0x7ffffff;
int n,m,a[maxn],b[maxn],f[maxn][maxn],path[maxn][maxn],len[maxn],ed;
int main(){
read(n);
for(ri i=1;i<=n;i++){
read(a[i]);
}
read(m);
for(ri i=1;i<=m;i++){
read(b[i]);
}
int ans=-inf,val,lst=0;
for(ri i=1;i<=n;i++){
lst=0;
val=f[i-1][0];
for(ri j=1;j<=m;j++){
if(a[i]==b[j]){
if(val+1>f[i][j]){
f[i][j]=val+1;
for(ri k=1;k<=len[lst];k++)path[j][k]=path[lst][k];
len[j]=len[lst]+1;
}
}
else f[i][j]=f[i-1][j];
path[j][len[j]]=b[j];
if(f[i][j]>ans){
ans=f[i][j];
ed=j;
}
if(b[j]<a[i]){
if(val<f[i-1][j]){
val=f[i-1][j];
lst=j;
}
}
}
}
printf("%d\n",ans);
for(ri i=1;i<=len[ed];i++)printf("%d ",path[ed][i]);
return 0;
}
|
方法3
既然$f[i][j]$是由$f[i-1][k]_{b[k]<b[j]}$转移过来,我们直接用个$f[i]$数组记录,然后每次学习方法2记录决策变量$t$,这样还能满足每个$f[t]$都是上个阶段的.
为什么呢,因为我们的代码已经保证了$a[i]>b[t]$,所以用来更新$j$的$f[t]$不可能在这个阶段中被更新过,所以我们也可以大胆地直接记录路径
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
48
49
50
51
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#define ll long long
#define ri register int
using std::min;
using std::max;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=705;
const int inf=0x7fffffff;
int f[maxn],a[maxn],b[maxn],pre[maxn];
int n,m;
void print(int x){
if(!x)return ;
print(pre[x]);
printf("%d ",b[x]);
return ;
}
int main(){
int ed=0,t=0;
memset(pre,0,sizeof(pre));
read(n);
for(ri i=1;i<=n;i++)read(a[i]);
read(m);
for(ri i=1;i<=m;i++)read(b[i]);
f[0]=0;
for(ri i=1;i<=n;i++){
t=0;
for(ri j=1;j<=m;j++){
if(a[i]==b[j]){
f[j]=f[t]+1;
pre[j]=t;
}
if(a[i]>b[j]&&f[j]>f[t])t=j;
}
}
for(ri i=1;i<=m;i++)if(f[ed]<f[i])ed=i;
printf("%d\n",f[ed]);
print(ed);
puts("");
return 0;
}
|