1692_Crossed Matchings.doc

解题报告：Crossed Matchings题目来源： poj 1692解法或类型： 动态规划作者：陈子沣DescriptionThere 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. InputThe first line of the input is the number M, which is the number of test cases (1 = M = 10). Each test case has three lines. The first line contains N1 and N2, the number of integers on the first and the second row respectively. The next line contains N1 integers which are the numbers on the first row. The third line contains N2 integers which are the numbers on the second row. All numbers are positive integers less than 100.OutputOutput should have one separate line for each test case. The maximum number of matching segments for each test case should be written in one separate line.解题思路：将相互交叉的两组匹配记作一个基本单元。根据题意就是要找到尽可能多的相互不重叠的基本单元的组合。考虑以下两种情况。解法一：一个基本单元左上和右下两个数已经确定，那么最合算的情况有两种。一种是第一行的两数距离最近；另一种是第二行的两数距离最近。其它的情况所占的“空间”必然包含着两种情况的一种，因此不用考虑。将所有这样的基本单元找出，以最左边两个数从左到右的顺序存储在数组Match（Matchi0Matchi3分别记录第i个基本单元中左上、右上、左下、右下四个数的位置）中。将fj记作以第j个基本单元为最左边基本单元的最优解中单元的个数。具有最优子结构。动态方程为：fi=maxfj+1 | Matchi1Matchj0且Matchi3Matchj2最后解为maxfi*2。解法二：一个基本单元的最右边两个数已经确定，那么最合算的情况就是第一行与第二行两个数的距离都最近。其它情况所占“空间”必然包含这种情况，因此不用考虑。将fij记作第一行第i个数及其左边第二行第j个数及其左边的最优解中基本单元的个数。具有最优子结构。动态方程为：fij=maxfij-1,fi-1j,fli-1lj-1+1（li、lj分别为最合算情况基本单元左上、左下两个数的位置）最后解为fN1N2*2。优化：可以发现对于每一个i、j都要单独计算相应的li、lj，这是时间上的浪费。将f1ij记作第二行第j个数左边距离最近的与第一行第i个数相等的数的位置。类似的将f2ij记作第一行第i个数左边距离最近的与第二行第j个数相等的数的位置。具有最优子结构。动态方程为：f1ij=j-1(r1i=r2j-1) f1ij-1(r1i!=r2j-1)f2ij=i-1(r1i-1=r2j) f1i-1j(r1i-1!=r2j)用预处理得到的f1ij、f2ij代替需要每次计算的lj、li。数据结构：用两个数组r11N1、r21N2分别存储第一行与第二行的数。其余详见解题思路。时空分析：解法一：时间：O(N1*N2)2)空间：O(N1*N2)解法二：时间：O(N1*N2)空间：O(N1*N2)源程序：解法一：#include const int MAXN=101;int M,N1,N2,r1MAXN,r2MAXN;void main()bool flag;int i,j,li,lj,t,s,max,fMAXN*MAXN*2,MatchMAXN*MAXN*24;scanf(%d,&M);while(M)s=0;scanf(%d%d,&N1,&N2);for(i=1;i=N1;i+) scanf(%d,&r1i);for(i=1;i=N2;i+) scanf(%d,&r2i);for(i=1;iN1;i+)for(j=2;j=N2;j+)if(r1i=r2j)flag=true;for(li=i+1;(li0)&flag;lj-)if(r1li=r2lj)&(r1li!=r1i)s+;Matchs0=i;Matchs1=li;Matchs2=lj;Matchs3=j;flag=false;if(flag=false) t=Matchs2; else t=0;flag=true;for(lj=j-1;(ljt)&flag;lj-)for(li=i+1;(li=N1)&flag;li+)if(r1li=r2lj)&(r1li!=r1i)s+;Matchs0=i;Matchs1=li;Matchs2=lj;Matchs3=j;flag=false;for(i=1;i0;i-)max=0;for(j=i+1;j=s;j+)if(Matchi1Matchj0)&(Matchi3Matchj2)&(maxfj) max=fj;fi+=max;max=0;for(i=1;i=s;i+)if(maxfi) max=fi;printf(%dn,max*2);M-;解法二未优化：#include const int MAXN=101;int M,N1,N2,r1MAXN,r2MAXN;void main()int i,j,li,lj,max,fMAXNMAXN=0;scanf(%d,&M);while(M)scanf(%d%d,&N1,&N2);for(i=1;i=N1;i+) scanf(%d,&r1i);for(i=1;i=N2;i+) scanf(%d,&r2i);for(i=2;i=N1;i+)for(j=2;j=N2;j+)max=fij-1;if(max0)&(r1li!=r2j);li-);if(li0) for(lj=j-1;(lj0)&(r1i!=r2lj);lj-);if(li0)&(lj0)&(fli-1lj-1+1max) max=fli-1lj-1+1;fij=max;printf(%dn,fN1N2*2);M-;解法二优化：#include const int MAXN=101;int M,N1,N2,r1MAXN,r2MAXN;void main()int i,j,max,fMAXNMAXN=0,f1MAXNMAXN,f2MAXNMAXN;scanf(%d,&M);while(M)scanf(%d%d,&N1,&N2);for(i=1;i=N1;i+) scanf(%d,&r1i);for(i=1;i=N2;i+) scanf(%d,&r2i);f121=0;for(i=2;i=N1;i+)for(j=2;j=N2;j+)if(r1i=r2j-1) f1ij=j-1;else f1ij=f1ij-1;f212=0;for(j=