爆搜的思路不难想到,就是将翻折的操作进行模拟,再将翻折后的数组进行 dfs 然后重复该操作。
但是处理翻折操作十分复杂,中间的细节很多。
-
首先纸条可以翻转,大部分人都看到了,所以在爆搜中加入了翻转的操作,但只需要在判定时反向的也判一次就行了,至于正确性你们可以自行思考。
-
纸条的翻折可以分为折痕在左边还是在右边,进行分类处理即可。
Accepted Code
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N], b[N], n, m;
bool flag;
void dfs(int num[], int len)
{
if (len < m || flag)return;
int tmp[N];
for (int i = 1; i <= len; i++)tmp[i] = num[i];
if (len == m)
{
bool pos1 = 1, pos2 = 1;
for (int i = 1; i <= len; i++)
if (num[i] != b[i])
{
pos1 = 0;
break;
}
for (int i = 1; i <= len; i++)
if (num[len - i + 1] != b[i])
{
pos2 = 0;
break;
}
if (pos1 || pos2)
{
flag = 1;
return;
}
}
for (int i = 1; i < len; i++)
{
for (int j = 1; j <= len; j++)tmp[j] = num[j];
if (max(len - i, i) < m)continue;
if (i <= len / 2)
{
for (int j = len, k = 1; k <= len - i; j--, k++)tmp[k] = num[j];
for (int j = len - i, k = i; k; j--, k--)tmp[j] += num[k];
}
else
{
for (int j = 1; j <= len; j++)tmp[j] = num[j];
for (int j = i, k = i + 1; k <= len; j--, k++)tmp[j] += num[k];
}
dfs(tmp, max(len - i, i));
}
}
int main()
{
while (cin >> n)
{
for (int i = 1; i <= n; i++)cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++)cin >> b[i];
flag = 0;
dfs(a, n);
cout << (flag ? "S\n" : "N\n");
}
return 0;
}