记忆化搜索(DFS+DP) URAL 1501 Sense of Beauty-白红宇

记忆化搜索(DFS+DP) URAL 1501 Sense of Beauty

阅读量：4355 次

发布时间：2019-06-07

本文共 1407 字，大约阅读时间需要 4 分钟。

1 /* 2     题意：给了两堆牌，每次从首部取出一张牌，按颜色分配到两个新堆，分配过程两新堆的总数差不大于1 3     记忆化搜索(DFS+DP)：我们思考如果我们将连续的两个操作看成一个集体操作，那么这个操作必然是1红1黑 4     考虑三种情况：a[]连续两个颜色相同，输出11；b[]连续两个相同，输出22； 5                     a[x] != b[y], 输出12；否则Impossible 6     详细解释：http://blog.csdn.net/jsun_moon/article/details/10254417 7 */ 8 #include 
     
       9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 using namespace std;15 16 const int MAXN = 1e3 + 10;17 const int INF = 0x3f3f3f3f;18 char a[MAXN], b[MAXN];19 bool dp[MAXN][MAXN];20 21 bool DFS(int x, int y)22 {23 if (!x && !y) return true;24 if (!dp[x][y]) dp[x][y] = true;25 else return false;26 27 if ((x-2)>=0 && a[x] != a[x-1] && DFS (x-2, y))28 {29 printf ("11"); return true;30 }31 if ((y-2)>=0 && b[y] != b[y-1] && DFS (x, y-2))32 {33 printf ("22"); return true;34 }35 if ((x-1)>=0 && (y-1)>=0 && a[x] != b[y] && DFS (x-1, y-1))36 {37 printf ("12"); return true;38 }39 40 return false;41 }42 43 int main(void) //URAL 1501 Sense of Beauty44 {45 //freopen ("V.in", "r", stdin);46 47 int n;48 while (scanf ("%d", &n) == 1)49 {50 memset (dp, false, sizeof (dp));51 scanf ("%s", a+1); scanf ("%s", b+1); 52 53 if (!DFS (n, n)) puts ("Impossible");54 else puts ("");55 }56 57 return 0;58 }59 60 /*61 Impossible62 */