ybtoj折纸问题

！！！更快的暴搜！！！

这是道搜索题

但是，这题不用老老实实的翻折搜索。

我们在枚举翻折点的时候可以直接从后半部分开始枚举，这样复杂度直接降了一半。

为什么？

想象一下，把一个纸条的左半部分反过来，是不是就等价于先把纸条整体翻过来，再翻折纸条的右边，所以我们可以用整体翻折以及之后翻折后半部分等效替代翻前面的，搜索的时候记得正着查一遍再反着查一遍，因为翻折后是对称的。

#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
int flag,n,m,a[21],b[21],c[21];
void dfs(int len,int f){
    if(flag )return;
    if(len == m){
        int f1 = 1,f2 = 1;
        for(int i=1;i<=len;++i){
            if(f1 || f2){
                if(a[i] != b[i])f1 = 0;
                if(a[i] != b[m-i+1])f2 = 0;
            }
            else break;
        }
        if(f1 || f2)flag = 1;//正反判断 
        return;
    }
    int d[21];//就是这里！！！！！回溯用的数组一定开在搜索内部，我就开了全局变量一直WA ，我***** 
    for(int i=1;i<=len;++i)d[i] = a[i];
    int mid = (len + 1) /2,s = (mid > m) ? mid : m;//不能翻折后比m短，小剪枝 
    for(int i=s;ii){
        int l = i,r = i+1;
        while(l && r <= len)
            a[l--]+=a[r++];
        dfs(i,0);
        for(int j=1;j<=len;++j)a[j] = d[j];//回溯 
    }
    if(!f){//整体翻折 
        for(int i=1;i<=len;++i)a[i] = d[len-i+1];
        dfs(len,1);
    }
}
int main(){
    while(scanf("%d",&n) == 1){
        flag = 0;
        for(int i=1;i<=n;++i)scanf("%d",a+i);
        scanf("%d",&m);
        for(int i=1;i<=m;++i)scanf("%d",b+i);
        dfs(n,0);
        puts(flag ? "S" : "N");
    }
}