[Acwing] 272. 最长公共上升子序列 动态规划

前言

传送门:

思路

状态表示 : f [ i ] [ j ] f[i][j] f[i][j] 前 i i i个 a [ ] a[] a[] 中以 b [ j ] b[j] b[j]结尾的最大公共上升子序列长度

状态计算 : f [ i ] [ j ] = f [ i − 1 ] [ j ] ( a [ i ] ! = b [ j ] ) f[i][j]=f[i-1][j](a[i]!=b[j]) f[i][j]=f[i−1][j](a[i]!=b[j]) f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ t ] + 1 ) ( a [ i ] = = b [ j ] ) f[i][j]=max(f[i-1][j],f[i-1][t]+1)(a[i] ==b[j]) f[i][j]=max(f[i−1][j],f[i−1][t]+1)(a[i]==b[j])

t t t依据的是子序列中倒数第二个数是哪个数

显然两个转移都与 i − 1 i-1 i−1层有关,所以我们直接可以从 i − 1 i-1 i−1层转移

同时又因为 f [ i − 1 ] [ t ] + 1 f[i-1][t]+1 f[i−1][t]+1使用到的每次都是最大值,因此我们可以边转移边维护一个最大值

Mycode

const int N = 3e3+10;
int f[N][N];
int a[N] , b[N];
int n;

void solve(){
	cin>>n;
	for(int i=1;i>a[i];
	for(int i=1;i>b[i];
	
	for(int i=1;i