CF10D LCIS
叶枫
2019-09-03 20:49:52
一道经典$DP$
### $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])$$
最后，再转移时储存位置，输出
### $Code~One$
二维
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#define ll long long
#define maxn 550
#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][maxn],g[maxn][maxn];
inline void put(int x){
if(!x) return;
put(g[n][x]);
printf("%d ",b[x]);
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
int m=read(),p=0;
for(int i=1;i<=m;i++) b[i]=read();
for(int i=1,t=0;i<=n;++i,t=0)
for(int j=1;j<=m;++j){
f[i][j]=f[i-1][j];
g[i][j]=g[i-1][j];
if(a[i]==b[j]&&f[i-1][t]+1>f[i][j]){
f[i][j]=f[i-1][t]+1;
g[i][j]=t;
}
if(b[j]<a[i]&&f[i-1][j]>f[i-1][t]) t=j;
//检查t是否为最长LCIS的结尾元素位置
}
for(int i=1;i<=m;i++)
if(f[n][i]>f[n][p]) p=i;
printf("%d\n",f[n][p]);
put(p);
return 0;
}
```
### 优化
分析状态转移方程可知`f[i][j]`都是由`f[i-1][j]`得来的，因此可以优化空间，设`f[i]`代表的是`a`序列前`i`个元素与`b`序列的`LCIS`长度，`t`为最长`LCIS`的结尾元素位置，新的状态转移方程为
$$f[i]=f[t]+1~(a[i]=b[j])$$
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#define ll long long
#define maxn 550
#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],g[maxn];
inline void put(int x){
if(!x) return;
put(g[x]);
printf("%d ",b[x]);
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
int m=read(),p=0;
for(int i=1;i<=m;i++) b[i]=read();
for(int i=1,t=0;i<=n;++i,t=0)
for(int j=1;j<=m;++j){
if(a[i]==b[j]){
f[j]=f[t]+1;
g[j]=t;
}
if(b[j]<a[i]&&f[j]>f[t]) t=j;
}
for(int i=1;i<=m;i++)
if(f[i]>f[p]) p=i;
printf("%d\n",f[p]);
put(p);
return 0;
}
```
效果显著
$P.S$可以写写[Acwing 272](https://www.acwing.com/problem/content/274/)