hdu4665 DFS

题意:

给你一个字符串,问你能不能拆成两个相同的字符串,顺序不能改变.

思路:

咋一看数据有点大,搜索过不去,但想想优化的地方很多,而且每个字母最多出现四次,所以多几个剪纸应该会过.

#include<stdio.h>

#include<string.h>

#define N 2000 + 10



int ans1[N] ,ans2[N];

int s1[N] ,s2[N] ,s[N];

int num[N] ,now[N] ,n;

int ok;

bool okk1(int l1 ,int l2 ,int id)

{

   if(s1[num[id]] >= s[num[id]] / 2)

   return 0;

   if(l1 >= l2) return 1;

   else if(num[id] == ans2[l1]) return 1;

   else return 0;

}

bool okk2(int l1 ,int l2 ,int id)

{

   if(l2 >= l1) return 1;

   else if(num[id] == ans1[l2]) return 1;

   else return 0;

}

void DFS(int l1 ,int l2 ,int id)

{

   if(ok) return ;

   if(l1 > n / 2 + 1 || l2 > n / 2 + 1)

   return;

   if(l1 == n / 2 + 1 && l2 == n / 2 + 1)

   {

      ok = 1;

      return ;

   }

   if(okk1(l1 ,l2 ,id) && !ok)

   {

      now[id] = 0;

      ans1[l1] = num[id];

      s1[now[id]] ++;

      DFS(l1 + 1 ,l2 ,id + 1);

      s1[now[id]] --;

   }

   if(okk2(l1 ,l2 ,id) && !ok)

   {

      now[id] = 1;

      ans2[l2] = num[id];

      s2[num[id]] ++;

      DFS(l1 ,l2 + 1 ,id + 1);

      s2[num[id]] --;

   }

}

int main ()

{

   int t ,i;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      memset(s ,0 ,sizeof(s));

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

      {

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

         s[num[i]] ++;

         s1[i] = s2[i] = 0;

      }

      ok = 0;

      DFS(1 ,1 ,1);

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

      printf("%d" ,now[i]);

      printf("%d\n" ,now[i]);

   }

   return 0;

}

巴特西

hdu4665 DFS

最新文章

热门文章