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