本来暴力写个TLE了，加上记忆化就A了。
1 #include <cstring> 2 #include <cstdio> 3 #include <string> 4 #include <iostream> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 int pre[1001][1001]; 9 int flag[1001][1001]; 10 char s1[1001],s2[1001]; 11 int sum1[1001],sum2[1001]; 12 int n; 13 int que[3001]; 14 int dfs(int x,int y) 15 { 16 if(x == n&&y == n) 17 return 1; 18 if(flag[x][y] == 2) 19 return 0; 20 else if(flag[x][y] == 1) 21 return 1; 22 if(x+1 <= n) 23 { 24 if(abs(sum1[x+1] + sum2[y]-(x+1+y-sum1[x+1]-sum2[y])) <= 1) 25 { 26 pre[x+1][y] = 1; 27 if(dfs(x+1,y)) 28 return flag[x+1][y] = 1; 29 else 30 { 31 flag[x+1][y] = 2; 32 pre[x+1][y] = 0; 33 } 34 } 35 } 36 if(y+1 <= n) 37 { 38 if(abs(sum1[x] + sum2[y+1]-(x+y+1-sum1[x]-sum2[y+1])) <= 1) 39 { 40 pre[x][y+1] = 2; 41 if(dfs(x,y+1)) 42 return flag[x][y+1] = 1; 43 else 44 { 45 flag[x][y+1] = 2; 46 pre[x][y+1] = 0; 47 } 48 } 49 } 50 return 0; 51 } 52 int main() 53 { 54 int i,x,y; 55 scanf("%d%s%s",&n,s1,s2); 56 if(s1[0] == '1') 57 sum1[1] = 1; 58 if(s2[0] == '1') 59 sum2[1] = 1; 60 for(i = 2;i <= n;i ++) 61 { 62 if(s1[i-1] == '1') 63 sum1[i] = sum1[i-1] + 1; 64 else 65 sum1[i] = sum1[i-1]; 66 if(s2[i-1] == '1') 67 sum2[i] = sum2[i-1] + 1; 68 else 69 sum2[i] = sum2[i-1]; 70 } 71 if(dfs(0,0)) 72 { 73 x = n; 74 y = n; 75 int m = 0; 76 while(x != 0||y != 0) 77 { 78 que[m++] = pre[x][y]; 79 if(pre[x][y] == 1) 80 x --; 81 else 82 y --; 83 } 84 for(i = m-1;i >= 0;i --) 85 printf("%d",que[i]); 86 printf(" "); 87 } 88 else 89 printf("Impossible "); 90 return 0; 91 }