Codeforces Beta Round #10D题

核心思路及完整代码

fi,jf_{i,j}表示aa中前ii个与bb中前jj个的LCIS

fi,j={fi,j1,  aibjmaxk=0j1{dpi1,k+1},  bk<ai and  ai=bjf_{i,j}= \begin{cases} \begin{aligned} &f_{i,j-1},\ \ &a_i\neq b_j\\ &\max_{k=0}^{j-1}\{dp_{i-1,k}+1\}, \ \ &b_k<a_i\ and \ \ a_i=b_j \end{aligned} \end{cases}

时间复杂度Θ(n3)\Theta(n^3)

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define ll long long
#define DE(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG(a) DE("DEBUG: %d\n",a)
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
int read() {
int x=0,f=1,ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

const int MAXN=500+10;

int n,m,a[MAXN],b[MAXN],dp[MAXN][MAXN],ans[MAXN][MAXN];

void print(int j) {
if(!j) return ;
print(ans[n][j]);
printf("%d ",b[j]-1);
}

int main() {
n=read(),m;
REP(i,1,n) a[i]=read()+1;
m=read();
REP(i,1,m) b[i]=read()+1;

REP(i,1,n) REP(j,1,m) {
ans[i][j]=ans[i-1][j];
if(a[i]!=b[j]) dp[i][j]=dp[i-1][j];
else {
REP(k,0,j-1)
if(b[k]<a[i]) {
if(dp[i-1][k]+1>dp[i][j]) {
dp[i][j]=dp[i-1][k]+1;
ans[i][j]=k;
}
}
}
}

int pos=0,ans=0;
REP(i,1,m) if(dp[n][i]>ans) ans=dp[n][i],pos=i;
printf("%d\n",ans);
print(pos);
return 0;
}

每次kk都从00开始检查到j1j-1浪费了时间,只需要记录下上次的结果和计算一下bj1b_{j-1}aia_i关系即可。

fi,j={fi,j1,  aibjmax{max,bj1}+1,  bj1<ai and  ai=bjmax,  bj1aif_{i,j}= \begin{cases} \begin{aligned} &f_{i,j-1},\ \ &a_i\neq b_j\\ &\max\{max',b_{j-1}\}+1, \ \ &b_{j-1}<a_i\ and \ \ a_i=b_j\\ &max', \ \ &b_{j-1}\geq a_i \end{aligned} \end{cases}

时间复杂度Θ(n2)\Theta(n^2)

我就没写了,大家去查xgzc、M_sea的啊。

评论