LCIS

要用dp的思路想这题

【题目链接】LCIS

【题目类型】dp

&题意：

给定两个序列，求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的，比如(x,x+1,...,y−1,y).

&题解：

一定要抓住递增的子序列是连续的这一条件，那么dp方程就是 dp[a[i]] = max(dp[a[i]], dp[a[i]-1] + 1);

发现其实可以简化为 dp[a[i]] = dp[a[i]-1] + 1；因为计算过程中dp[a[i]]不会降低

对两个序列都求一遍，然后取两者dp值的最小值的最大值

【时间复杂度】O(n)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define rep(i,b) for(int i=0;i<(b);i++)

const int MAXN = 100000 + 5 ;

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

int f[MAXN],g[MAXN];

void Solve()

{

	cle(f,0); cle(g,0);

	SII(n,m);

	rep(i,n) SI(a[i]);

	rep(i,m) SI(b[i]);

	rep(i,n) f[a[i]]=f[a[i]-1]+1;

	rep(i,m) g[b[i]]=g[b[i]-1]+1;

	int ans=0;

	rep(i,MAXN) ans=max(ans,min(f[i],g[i]));

	printf("%d\n",ans);

}

int main()

{

	int T;cin>>T;while(T--)

	Solve();

	return 0;

}