文章目录
题目大意
捆绑数据，害人不浅。
说白了，就是最长公共上升子序列
题解：
初始思想——暴力20%
也不用讲，
O
(
2
n
)
O(2^n)
O(2n)枚举。
来个朴实无华的代码：
#include<bits/stdc++.h> //by 马老师
using namespace std;
int a[10005],b[10005],f[10005];
int n,m;
bool xs(int jg,int djg,int u)
{
if(djg==jg)
{
int t=1;
for(int i=1;i<=n;i++)
{
if(n-i<jg-t)
{
return false;
}
if(f[t]==a[i])
{
t++;
}
if(t>jg)
{
printf("%d\n",jg);
for(int j=1;j<=jg;j++)
{
printf("%d ",f[j]);
}
return true;
}
}
}
for(int i=u+1;i<=m;i++)
{
if(b[i]<=f[djg])
{
continue;
}
f[++djg]=b[i];
if(xs(jg,djg,i))
{
return true;
}
--djg;
}
return false;
}
int main()
{
freopen("okarin.in","r",stdin);
freopen("okarin.out","w",stdout);
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=m;i>=1;i--)
{
if(xs(i,0,0))
{
return 0;
}
}
printf("0");
return 0;
}
初步深入——DP45%
开始看，
n
n
n，
m
m
m都这么小，是不是DP？？？
怎么设？？？
d
p
[
i
,
j
]
dp[i,j]
dp[i,j]为取到
α
\alpha
α世界线和
β
\beta
β世界线，且取了
β
j
\beta_j
βj的最长公共上升子序列。
考虑转移…(设
α
\alpha
α为
a
a
a,
β
\beta
β为
b
b
b)
如有
k
k
k，满足
k
<
j
,
b
k
<
a
i
k<j,b_k<a_i
k<j,bk<ai，我们就能
d
p
[
i
,
j
]
=
d
p
[
i
−
1
]
[
k
]
+
1
(
a
[
i
]
=
=
b
[
j
]
)
dp[i,j]=dp[i-1][k]+1(a[i]==b[j])
dp[i,j]=dp[i−1][k]+1(a[i]==b[j])
不用说都明白吧，打代码啊！！！
100就是个优化
深入探索——优化100%
首先考虑如何快速求
k
k
k…
因为
d
p
[
i
,
j
]
dp[i,j]
dp[i,j]由
d
p
[
i
−
1
]
[
k
]
dp[i-1][k]
dp[i−1][k]推上来，
所以如果
d
p
[
i
−
1
]
[
k
1
]
dp[i-1][k_1]
dp[i−1][k1]比
d
p
[
i
−
1
]
[
k
2
]
dp[i-1][k_2]
dp[i−1][k2]小，那么
k
1
k_1
k1是不是废了。
由此，我们可以推出线性，优化成
O
(
n
m
)
O(nm)
O(nm)。
Fu(i,1,n){
int k=0;
Fu(j,1,m){
f[i][j]=f[i-1][j],pre[i][j]=j;
if(b[j]==a[i]&&f[i-1][k]+1>f[i][j]){
f[i][j]=f[i-1][k]+1;
pre[i][j]=k;
}
if(b[j]<a[i]&&f[i-1][k]<=f[i][j]) k=j;
}
}
Q：如何输出路径
void dfs(int o,int u){
if(o==0||u==0) return ;
dfs(o-1,pre[o][u]);
if(u!=pre[o][u]) printf("%d ",b[u]);
}
参考代码
#include<bits/stdc++.h>
#define rg register
#define Fu(i,a,b) for(rg int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(rg int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,m,f[5005][5005],pre[5005][5005],a[5005],b[5005],u,last;
int c[5005];
void dfs(int o,int u){
if(o==0||u==0) return ;
dfs(o-1,pre[o][u]);
if(u!=pre[o][u]) printf("%d ",b[u]);
}
int main(){
fre(okarin);
scanf("%d",&n);
Fu(i,1,n) scanf("%d",&a[i]);
scanf("%d",&m);
Fu(i,1,m) scanf("%d",&b[i]);
Fu(i,1,n){
int k=0;
Fu(j,1,m){
f[i][j]=f[i-1][j],pre[i][j]=j;
if(b[j]==a[i]&&f[i-1][k]+1>f[i][j]){
f[i][j]=f[i-1][k]+1;
pre[i][j]=k;
}
if(b[j]<a[i]&&f[i-1][k]<=f[i][j]) k=j;
}
}
Fu(i,1,m) if(f[n][u]<f[n][i]) u=i;
printf("%d\n",f[n][u]);
dfs(n,u);
Fd(i,c[0],1) printf("%d ",c[i]);
return 0;
}