回溯搜索

不知道这个算不算剪枝，小白一个......

题目描述:
给出一个长度为n的数列A𝑖，问是否能将这个数列分解为两个长度
为n/2的子序列，满足
∙ 两个子序列不互相重叠。
∙ 两个子序列中的数要完全一样，{1, 2} = {1, 2}，{1, 2} ≠ {2, 1}。
输入描述:
第一行，一个正整数T，表示数据组数。
接下来T组数据，每组数据的第一行，一个正整数n，第二行𝑛个正整数A𝑖。
输出描述:
每组数据输出一行，如果可以完成，输出Frederica Bernkastel，否则输出Furude Rika。

示例1
输入

复制
3
4
1 1 2 2
6
1 2 3 4 5 6
4
1 2 2 1
输出

复制
Frederica Bernkastel
Furude Rika
Furude Rika

解题思路：
1.考虑数据的大小，直接搜索必然超时，所以考虑用空间节约时间的方法。创建2个数组用来保存数字，进行匹配。
2.考虑用三指针的思想来处理数据，aIndex,bIndex,arrIndex，分别对应三个数组的索引（三个指针）.
3.搜索方法是首先将arr第一个数字默认放进a数组里，遍历原数组arr,同时进行判定，是否是b数组索引对应的a数组的数字（这里可能有点绕，其实就是相匹配的数字）。
4.搜索面对的是两种情况:
相匹配的情况下，就可以尝试（用if去尝试 ）去放进b数组之中，如果不行，就放进a数组之中；
不匹配的话直接放进a数组之中。
5.终止条件首先判断是否超出一半，其次是未超出一半的同时，arr数组遍历完毕(代表互相匹配成功）

int arr[50],a[50],b[50];
int aIndex, bIndex, arrIndex;//三个数组索引 a 和 b 的索引也代表他们的数字个数
#include<iostream>
int n;
using namespace std;

// 其实就两种情况  判断arr里面的这个数字 是否对应 不对应 直接丢a里  对应就去尝试丢b里面的情况 直到最后 来判断结果

int dfs(int aIndex, int bIndex, int arrIndex)
{

    if (aIndex > n / 2 || bIndex > n / 2)
    {
        return 0;
    }
    //数组都没用掉一半 
    if (arrIndex > n)
    {
        return 1;
    }
    if (arr[arrIndex] == a[bIndex+1])
    {
        b[bIndex + 1] = arr[arrIndex];
        if (dfs(aIndex, bIndex + 1, arrIndex+1))
        {
            return 1;
        }
        //回溯消除选择选择状态 
        b[bIndex + 1] = 0;//清除掉 可以省略 主要是思想的体现
    }
    a[aIndex + 1] = arr[arrIndex];
    return dfs(aIndex + 1, bIndex, arrIndex + 1);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> arr[i]; 
        }
        a[1] = arr[1];//先把一个丢进去
        if (dfs(1, 0, 2))
        {
            cout << "Frederica Bernkastel\n";
        }
        else
        {
            cout << "Furude Rika\n";
        }
    }
}