【POJ1692】Crossed Matchings(动态规划DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 10 日

There are two rows of positive integer numbers. We can draw one line segment between any two equal numbers, with values r, if one of them is located in the first row and the other one is located in the second row. We call this line segment an r-matching segment. The following figure shows a 3-matching and a 2-matching segment.
We want to find the maximum number of matching segments possible to draw for the given input, such that:
1. Each a-matching segment should cross exactly one b-matching segment, where a != b .
2. No two matching segments can be drawn from a number. For example, the following matchings are not allowed.
Write a program to compute the maximum number of matching segments for the input data. Note that this number is always even.
题意:给出两行数,求上下匹配的最多组数是多少。
匹配规则
1,匹配对的数字必须相同
2.每个匹配必须有且只能有一个匹配与之相交叉,且相交叉的两组匹配数字必须不同
2,一个数最多只能匹配一次
方法:DP
分析:用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]:
a.则第一行从i往前扫,直到扫到第一个a[k1]==b[j](k1 #include <iostream> #include <algorithm> using namespace std; int dp[102][102]; int a[102],b[102]; int n,m; int main(){ int i,j,t,k1,k2; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(j=1;j<=m;j++) scanf("%d",&b[j]); memset(dp,0,sizeof(dp)); for(i=2;i<=n;i++) for(j=2;j<=m;j++){ dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1])); if(a[i]!=b[j]){ for(k1=i-1;k1>=1;k1--) if(a[k1]==b[j])break; for(k2=j-1;k2>=1;k2--) if(a[i]==b[k2])break; if(k1&&k2) dp[i][j]=max(dp[i][j],dp[k1-1][k2-1]+2); } } printf("%d\n",dp[n][m]); } }

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日