CH5101 LCIS（最长公共上升子序列）题解

每日一题 day16 打卡

Analysis

设F[i,j]表示A[1..i]与B[1..j]并且以B[j]结尾的两段最长公共上升子序列，那么我们可以发现这样的转移

（1）A[i]==B[j]时

F[i][j]=max(F[i-1][k])+1,其中k满足1<=k<=j并且B[j]<A[i].

(2)如果不相等：

F[i][j]=F[i-1][j]

这样我们三重循环就可以搞定。但是这里是可以优化的。

我们考虑这样的一个事实：我们知道这样的一个事实，再第二层循环的时候，我们其实在枚举j。我们把满足条件的k叫做决策集合：S（i，j)。在j增加的时候，我们需要判断j是否可以被加入这个集合。所以我们需要检查：B[j]和A[i]的大小关系。如果满足b[j]<a[i]，那么我们就可以把他加入新的集合，这个时候我们只需要记录上一次的最大值，没必要在循环找一遍。这样就可以优化一层循环。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

#define maxn 3000+10

using namespace std;

inline int read()

{

    int x=0;

    bool f=1;

    char c=getchar();

    for(; !isdigit(c); c=getchar()) if(c=='-') f=0;

    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';

    if(f) return x;

    return 0-x;

}

inline void write(int x)

{

    if(x<0){putchar('-');x=-x;}

    if(x>9)write(x/10);

    putchar(x%10+'0');

}

int n,ans;

int a[maxn],b[maxn],dp[maxn][maxn];

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++) dp[i][0]=dp[0][i]=0;

	for(int i=1;i<=n;i++)

	{

		int val=0;

		for(int j=1;j<=n;j++)

		{

			if(a[i]==b[j]) dp[i][j]=val+1;

			else dp[i][j]=dp[i-1][j];

			if(b[j]<a[i]) val=max(val,dp[i-1][j]);

		}

	}

	for(int i=1;i<=n;i++) ans=max(ans,dp[n][i]);

	write(ans);

	return 0;

}

巴特西

CH5101 LCIS（最长公共上升子序列）题解

Analysis

最新文章

热门文章

巴特西

CH5101 LCIS（最长公共上升子序列） 题解

Analysis

最新文章

热门文章

CH5101 LCIS（最长公共上升子序列）题解