ProblemH：⼩姐姐的QQ号（DFS）
Contest -
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 297 Solved: 20
Description
⼀天GJJ去超市购物，⼀位发传单的⼩姐姐给了他⼀张名⽚；GJJ看到名⽚上有⼩姐姐的QQ号，特别激动⼼想能不能将它分解成两段⼦序列，完全⼀样⼜不互相重叠呢（长度为总长度⼀半）？
雪的诗歌Input
多实例，每次第⼀⾏给出⼀个T，表⽰T组数据，如果T=0，则表⽰结束。
接下来每⼀组数据，第⼀⾏⼀个整数n (2<=n<=30且为偶数)。
第⼆⾏输⼊n个整数;
Output
如果可以输出“竟然还有这种操作”，否则输出“没有这种操作”；输出占⼀⾏
Sample Input
2
8
4 2 8 4 9 2 8 9
8
1 2 3 4 5 6 7 8
Sample Output
竟然还有这种操作
漫思茶
没有这种操作
HINT
第⼀个样例可以分解成两个完全⼀样的⼦序列 4 2 8 9和4 2 8 9；
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <map>
7 #include <queue>
8 #include <bits/stdc++.h>
9using namespace std;
10 typedef long long LL;
11const int N = 50;
12int a[N], b[N], c[N];
13int flag, n;
14void dfs(int pos,int len1,int len2,int st)//算法的奥秘
15{
皮疹怎么治疗16if(len1>n/2+1 ||len2>n/2+1 ||flag) return ;
17if(len1==n/2+1 && len2==n/2+1)
18 {
19 flag=1;
三天计划20return ;
21 }
雨痕22if(pos==1)
23 {
24 b[1]=a[1];
25 dfs(pos+1,len1+1,len2,st);
26 }
写作教学27el
28 {
29if(a[pos]==b[st])
30 {
31 c[len2]=a[pos];
32 dfs(pos+1,len1,len2+1,st+1);
33 }
34 b[len1]=a[pos];
35 dfs(pos+1,len1+1,len2,st);
36 }
37return ;
38}
39
40int main()
41{
组织考察
42int t;
43while(scanf("%d", &t),t!=0)
44 {
45while(t--)
46 {
47 flag=0;
48 scanf("%d", &n);
49for(int i=1; i<=n; i++) scanf("%d", &a[i]);
50 dfs(1,1,1,1);
如何去除茶垢51if(flag) printf("竟然还有这种操作\n");
52el printf("没有这种操作\n");
53 }
54 }
55
56return0;
57 }
题意：给⼀个长度为n的数组，判断是否可以将其分为两个完全相同长度为n/2的⼦序列；（⼦序列是指数字之间在原序列的前后顺序不变）
解：dfs，从起点遍历，开两个序列数组，
（1）当前遍历的位置如果和第⼀个序列中的相对应的位置相同则加⼊第⼆个序列中第⼀个序列的对应位置加1，
（2）或者加⼊第⼀个序列中延伸长度
//这种题看似很简单其实要是让我来写的话，我可能写不出来，⾥⾯⽤到了递归的思想，这种思想虽然是算法⾥⾯最基本的思想，但是理解起来还是有⼀定的难度的
