问题：

如下图所示。图中有两行正整数，每行中有若干个正整数。如果第一行的某个数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;
}