这道题可以把空间优化到一维
前置芝士
$LCS$
$$ f[i][j]=f[i-1][j-1]+1\;(i,j>0,a[i]=b[j])$$
$$ f[i][j]=max(f[i][j-1],f[i-1][j])\;(i,j>0,a[i]\not=b[j])$$
其中,f[i][j]
为a
序列前i
个元素与b
序列前j
个元素的$LCS$长度
$LIS$
$$f[i]=max~f[j]+1~(j<i,a[j]<a[i])$$
f[i]
为以第i
个元素结尾的$LIS$长度。
$LCIS$
我们想办法糅合这两种动态规划的思想,设f[i][j]
代表的是a
序列前i
个元素与b
序列前j
个元素的$LCIS$长度(最长公共上升子序列),t
为最长$LCIS$的结尾元素位置,我们可以推出状态转移方程
$$f[i][j]=f[i-1][j]~(a[i]\not=b[j])$$
$$f[i][j]=max(f[i-1][j],f[i-1][t]+1)~(a[i]=b[j])$$
但是这样二维的空间显然不优秀
优化
分析状态转移方程可知f[i][j]
都是由f[i-1][j]
得来的,因此可以优化空间,设f[i]
代表的是a
序列前i
个元素与b
序列的LCIS
长度,t
为最长LCIS
的结尾元素位置,新的状态转移方程为
$$f[i]=f[t]+1~(a[i]=b[j])$$
这样空间就降到了一维
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#define ll long long
#define maxn 3050
#define inf 2147483647
#define mod 10003
#define eps 1e-6
#define pi acos(-1.0)
#define de(x) ((x)*(x))
using namespace std;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,a[maxn],b[maxn],f[maxn],maxx;
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=n;i++){
maxx=0;
for(int j=1;j<=n;j++){
if(b[j]<a[i]&&maxx<f[j]) maxx=f[j];
if(b[j]==a[i]) f[j]=maxx+1;
}
}
maxx=0;
for(int i=1;i<=n;i++) if(maxx<f[i]) maxx=f[i];
printf("%d",maxx);
return 0;
}
大佬,我想问一下,你那个第二重循环里的两个if条件是不是写反了,虽然能AC,但这是数据问题吧?
反不反没影响,不可能同时满足的,只能满足b[j]=a[i]或者是b[j]<a[i]中其中一个
orz
tql
妙死爷了
tjl
orz
棒棒哒
赞👍
谢谢
棒棒哒