dfs+记忆化 对于当前状态虽然满足和差 但如果搜下去没有满足的情况也是不可以的 所以需要记忆化下
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
char s1[],s2[];
int dp[][];
int sum1,sum2;
int p[],n,flag;
int ss1[],ss2[];
int st1[],st2[];
int dfs(int x,int y,int v,int o)
{
if(flag)
return ;
if(dp[x][y]==)
return ;
if(o==)
p[v] = ;
else
p[v] = ;
int i;
if(v==*n)
{
for(i = ; i <= *n ; i++)
printf("%d",p[i]);
puts("");
flag = ;
return ;
}
if(y<n&&abs((ss1[x]+ss2[y+])-(st1[x]+st2[y+]))<=)
{ if(dfs(x,y+,v+,)==)
return dp[x][y+] = ;
else
dp[x][y+] = ;
}
if(x<n&&abs((ss1[x+]+ss2[y])-(st1[x+]+st2[y]))<=)
{
if(dfs(x+,y,v+,)==)
return dp[x+][y] = ;
else
dp[x+][y] = ;
}
}
int main()
{
int i,j,k;
scanf("%d",&n);
scanf("%s%s",s1,s2);
ss1[]=,ss2[]=;st1[] = ;st2[]=;
for(i = ; i < n ; i++)
if(s1[i]=='')
{
ss1[i+] = ss1[i]+;
st1[i+] = st1[i];
}
else
{
st1[i+] = st1[i]+;
ss1[i+] = ss1[i];
}
for(i = ; i < n ; i++)
if(s2[i]=='')
{
ss2[i+] = ss2[i]+;
st2[i+] = st2[i];
}
else
{
st2[i+] = st2[i]+;
ss2[i+] = ss2[i];
}
dfs(,,,);
if(!flag)
dfs(,,,);
if(!flag)
printf("Impossible\n");
return ;
}