【匹配线段问题】

问题：

如下图所示。图中有两行正整数，每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同，这样就可以在这两个正整数之间划一条线，并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。

                  

请编写完整程序，求最大的匹配线段数量，并使得这些匹配线段满足如下条件：

1. 每一个a-匹配线段必须与另一个b-匹配线段相交，且a不等于b.
2. 任何两个匹配线段不能从同一个整数出发。如下图中3-匹配线段是不合法的匹配线段。

     

    不满足上述两个条件的匹配线段则不能称之为匹配线段，不计入匹配线段的数量。例如有两行整数分别如下，则该例中其匹配线段的数量为6.

1 3 1 3 1 3

3 1 3 1 3 1

下面的匹配线段数量则为0。因为虽然最多可划4条匹配线段，但不满足这其中2条匹配线段相交且a-匹配线段不等于b匹配线段的条件，因此其匹配线段的数量为0.

1 1 3 3

1 1 3 3

思路：

回溯法。

第n层顺序考虑第1行的第n个正整数与第2行的某个正整数进行匹配，匹配后需要在一个一维向量中标记，代表下次不可以参与匹配。

当达到深度时，分支被目标函数截断，进行匹配线段的计算（也要找匹配，找到一定记得退出循环），那么将匹配线段数目与最优值作比较，更新最优值。

难点：匹配线段的计算函数，匹配对的存储。

代码：

#include<bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
int n;
int first[110];
int second[110];
int sign[110];
int best;int cal(int cnt, PII duple[])
{int result = 0;int sign[cnt+1] = {0};for(int i = 1; i <= cnt; i++){if(sign[i]) continue;for(int j = 1; j <= cnt; j++){if(first[duple[i].first] == first[duple[j].first]) continue;if((duple[i].first - duple[j].first) * (duple[i].second - duple[j].second) < 0){sign[i] = 1, result += 1;if(!sign[j]) sign[j] = 1, result += 1;break;}}}return result;
}
void dfs(int k, int cnt, PII duple[])
{if(k > n){int this_time = cal(cnt, duple);if(this_time > best) best = this_time;}for(int i = 1; i <= n; i++){if(second[i] != first[k]) continue;if(sign[i]) continue;sign[i] = 1;duple[cnt+1] = {k, i};dfs(k+1, cnt+1, duple);duple[cnt+1] = {}; sign[i] = 0;}
}
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> first[i];}for(int i = 1; i <= n; i++){cin >> second[i];}PII duple[110];dfs(1, 0, duple);cout << best << endl;return 0;
}