1400 序列分解(dfs)

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!

//难懂的题意，看了讨论才知道，就是说将大序列分成两个子序列，子序列的顺序关系不能改变，
那么没想到什么好办法，玄学dfs走一波,算起来复杂度高，实际是不怎么高的，毕竟要相同才能移动，想清楚即可

 #include <bits/stdc++.h>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define LL long long

 #define MX 45

 int n;

 int dat[MX];

 bool vis[MX];

 int dfs(int x, int y, int s)

 {

     if (s==n/) return ;

     vis[x]=, vis[y]=;

     int _x = x+, _y = y+;

     while (_x<=n&&vis[_x]) _x++;

     while()

     {

         while (_y<=n&&(vis[_y]||_y==_x||dat[_x]!=dat[_y])) _y++;

         if (_x<=n&&_y<=n)

         {

             if (dfs(_x,_y,s+))

                 return ;

             _y++;

         }

         else break;

     }

     vis[x]=, vis[y]=;

     return ;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while (T--)

     {

         memset(vis,,sizeof(vis));

         scanf("%d",&n);

         for (int i=;i<=n;i++)

             scanf("%d",&dat[i]);

         bool ok = ;

         for (int i=;i<=n/+;i++)

         {

             if (dat[]==dat[i]&&dfs(,i,))

             {

                 ok=;

                 break;

             }

         }

         if (ok)

             printf("Good job!!\n");

         else

             printf("What a pity!\n");

     }

 }

巴特西

1400 序列分解(dfs)

最新文章

热门文章