POJ 1692 Crossed Matchings

    xiaoxiao2021-03-26  4

    POJ 1692 Crossed Matchings

    dp

    传送门:HustOJ

    传送门:POJ


    题意

    给出两行数,求上下匹配的最多组数是多少。 匹配规则 1,匹配对的数字必须相同 2.每个匹配必须有且只能有一个匹配与之相交叉,且相交叉的两组匹配数字必须不同 2,一个数最多只能匹配一次


    分析

    用dp[i][j]表示第一行取i个数,第二行取j个数字的最多匹配项 对于某个dp[i][j]: 1. 不匹配第一行i个,或不匹配第二行第j个:dp[i][j]=Max(dp[i-1][j],dp[i][j-1]) 2. 如果a[i]==b[j],不产生新匹配,匹配结果为1的值 3. 若a[i]!=b[j]:

    则第一行从i往前扫,直到扫到第一个a[k1]==b[j](k1 b.同理,第二行从j往前扫,直到扫到第一个b[k2]==a[i](k2 若找不到这样的k1,k2则不能才产生新匹配,跳过 若存在这样的k1,k2,此时匹配(a[i],b[k2])、(a[k1],b[j])匹配, 才生新的匹配情形,匹配数量为:dp[k1-1][k2-1]+2. 最优dp[i][j]=Max(1,2,3);

    代码

    #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <cmath> #include <queue> #include <stack> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define M(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXN=1005; const int oo=0x3f3f3f3f; typedef __int64 LL; const LL loo=4223372036854775807ll; typedef long double LB; const LL mod=1e9+7; int r1[MAXN], r2[MAXN]; int dp[MAXN][MAXN]; int main() { _ int T;cin>>T; while(T--) { int n, m;cin>>n>>m; M(r1, 0);M(r2, 0);M(dp, 0); for(int i=1;i<=n;i++) cin>>r1[i]; for(int i=1;i<=m;i++) cin>>r2[i]; for(int i=2;i<=n;i++) { for(int j=2;j<=m;j++) { dp[i][j]=max(dp[i-1][j], dp[i][j-1]); if(r1[i]==r2[j]) continue; int k1=0, k2=0; for(k1=i-1;k1>=1;k1--) if(r1[k1]==r2[j]) break; for(k2=j-1;k2>=1;k2--) if(r2[k2]==r1[i]) break; if(k1>0&&k2>0) dp[i][j]=max(dp[i][j], dp[k1-1][k2-1]+2); } } cout<<dp[n][m]<<endl; } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-500380.html

    最新回复(0)