原题链接
1400 序列分解 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注小刀和大刀是双胞胎兄弟。今天他们玩一个有意思的游戏。 大刀给小刀准备了一个长度为n的整数序列。小刀试着把这个序列分解成两个长度为n/2的子序列。
这两个子序列必须满足以下两个条件：
1.他们不能相互重叠。
2.他们要完全一样。
如果小刀可以分解成功，大刀会给小刀一些糖果。
然而这个问题对于小刀来说太难了。他想请你来帮忙。
Input 第一行给出一个T，表示T组数据。(1<=T<=5) 接下来每一组数据，输入共2行。 第一行包含一个整数n (2<=n<=40且为偶数)。 第二行给出n个整数a[0],a[1],a[2],…,a[n-1]表示大刀给小刀准备的序列。(-1,000,000,000<=a[i]<=1,000,000,000) Output 如果小刀可以完成游戏，输出"Good job!!" (不包含引号)，否则 输出"What a pity!" (不包含引号)。 Input示例 2 4 1 1 2 2 6 1 2 3 4 5 6 Output示例 Good job!! What a pity!题解:给一个序列判断是否能分成两个完全一样，不重叠的子序列.(序列中元素之间的相对顺序是不变的)
直接深搜，对于序列中的每个数根据条件搜索在第一序列是否可行，在第二序列是否可行.
#include <iostream> #include <cstdio> #include <algorithm> #include <map> #define maxn 45 using namespace std; typedef long long ll; int num[maxn], p1[maxn], p2[maxn]; int n; bool dfs(int j, int k1, int k2){ if(n - k1 - k2 < k1 - k2) return false; if(k1 + k2 == n) return true; if(k1 == k2){ p1[k1] = num[j]; if(dfs(j+1, k1+1, k2)) return true; } else{ if(num[j] == p1[k2]){ p2[k2] = num[j]; if(dfs(j+1, k1, k2+1)) return true; } p1[k1] = num[j]; if(dfs(j+1, k1+1, k2)) return true; } return false; } int main(){ // freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", num+i); p1[0] = num[0]; if(dfs(1, 1, 0)) puts("Good job!!"); else puts("What a pity!"); } return 0; }
