首页 > 代码库 > UVA 12511/CSU 1120 virus 最长公共上升子序列

UVA 12511/CSU 1120 virus 最长公共上升子序列

2024-07-21 18:32:59   218人阅读

第一次接触一个这最长公共上升子序列

不过其实搞清楚了跟最长公共子序列和 最长上升子序列如出一辙

两重循环，对于当前不相等的，等于前一个的值，相等的，等于比当前A【i】小的最大值+1。弄个临时变量记录最大值即可

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int dp[2][1010];int A[1010],B[1010],n,m;int main(){    int t;    scanf("%d",&t);    while (t--)    {        scanf("%d",&n);        for (int i=1;i<=n;i++) scanf("%d",&A[i]);        scanf("%d",&m);        for (int i=1;i<=m;i++) scanf("%d",&B[i]);        memset(dp,0,sizeof dp);        int maxn=0;        int p=0;        for (int i=1;i<=n;i++){            maxn=0;            for (int j=1;j<=m;j++){                if (A[i]!=B[j]) dp[p][j]=dp[p^1][j];                else{                    dp[p][j]=maxn+1;                }                if (B[j]<A[i]) maxn=max(maxn,dp[p][j]);            }            p^=1;        }        int ans=0;        for (int i=1;i<=m;i++) ans=max(ans,dp[p^1][i]);        printf("%d\n",ans);    }}

　　

UVA 12511/CSU 1120 virus 最长公共上升子序列


联系
我们