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; }