| input | output |
|---|---|
4 0011 0110 |
22121112 |
4 1100 1100 |
Impossible |
题意：
给你两堆牌，牌的颜色只有红色或者黑色。 然后从两堆牌的牌顶来抽牌，每次抽可以选择两堆中的一堆。每次抽完，所得到的牌，红牌和黑牌数量相差必须不超过1。
做法：
因为一共各1000张牌，所以可以dp记忆化搜索。dp[i][j]代表 在第一堆牌抽了i张，第二堆牌抽了j张的情况下， 有没有不违反规则 达到这状态的方法。如果有 dp[i][j]会等于0，1，2，0表示当前多了一个黑牌，1表示当前红黑牌一样多，2表示当前红牌多一张。-2表示没达到这种状态的方法。
然后就是几种转移的方法，都要在dfs（i-1，j）或者 dfs(j,i-1) 可以达到的情况下 才能转移。
int dp[1100][1100];//
int n;
int num1[1100];
int num2[1100];
int bu[1100];
int dfs(int i,int j)
{
if(~dp[i][j])//不是-1，就返回已经有的值， 记忆化搜索，不然会超时
return dp[i][j];
if(i==0&&j==0)
return dp[i][j]=1;//0 0多 1平 2 1多
if(i!=0)
{
if(dfs(i-1,j)==0&&num1[i]==1)//这里表示，上一个状态 红黑牌中 红牌多，所以这次必须抽黑牌才能转移
{
bu[i+j]=1;
return dp[i][j]=1;
}
if(dfs(i-1,j)==1)
{
if(num1[i]==1)
{
bu[i+j]=1;
return dp[i][j]=2;
}
if(num1[i]==0)
{
bu[i+j]=1;
return dp[i][j]=0;
}
}
if(dfs(i-1,j)==2&&num1[i]==0)
{
bu[i+j]=1;
return dp[i][j]=1;
}
}
if(j!=0)
{
if(dfs(i,j-1)==0&&num2[j]==1)
{
bu[i+j]=2;
return dp[i][j]=1;
}
if(dfs(i,j-1)==1)
{
if(num2[j]==1)
{
bu[i+j]=2;
return dp[i][j]=2;
}
if(num2[j]==0)
{
bu[i+j]=2;
return dp[i][j]=0;
}
}
if(dfs(i,j-1)==2&&num2[j]==0)
{
bu[i+j]=2;
return dp[i][j]=1;
}
}
return dp[i][j]=-2;
}
char n1[1100];
char n2[1100];
int main()
{
while(scanf("%d",&n)!=EOF)
{
scanf("%s%s",n1,n2);
memset(dp,-1,sizeof dp);
for(int i=1;i<=n;i++)
{
num1[i]=n1[i-1]-'0';
num2[i]=n2[i-1]-'0';
}
if(dfs(n,n)!=-2)
{
for(int i=1;i<=2*n;i++)
printf("%d",bu[i]);
puts("");
}
else
puts("Impossible");
}
return 0;
}
原文：http://blog.csdn.net/u013532224/article/details/44698539