URAL 1501. Sense of Beauty(记忆化搜索 dfs)

题目链接:?space=1&num=1501

The owner of a casino for New Russians has a very refined sense of beauty. For example, after a game there remain two piles with the same number of cards on the table, and the owner likes the cards to be arranged into two piles according to the color: one pile with red cards and the other with black cards. Of course, this is done not by the owner himself, but by a croupier. The owner just likes to watch the process. The croupier takes a card from the top of one of the initial piles and puts it into one of the new piles; this is repeated until all the cards from the initial piles are transferred. The owner doesn’t like it if one of the resulting piles grows faster than the other. At each moment the resulting piles must not differ in size by more than one card; a bigger difference would contradict the owner’s sense of beauty. Help the croupier to arrange the cards according to the tastes of his owner.

Input

The first line of the input contains the numberNof cards in each of the piles (4 ≤N≤ 1000). Each of the next two lines containsNdigits 0 or 1 describing the piles: 1 denotes a red-suit card and 0 denotes a black-suit card. The cards in a pile are described from the top to the bottom. There are in totalNred andNblack cards in the two piles.

Output

Output a line containing 2Ndigits 1 or 2, which describes the process of transferring the cards. Each number shows the number of the pile from which a card is taken. If it is impossible to perform this task according to the given rules, output "Impossible".

Samples

inputoutput

40011011022121112

411001100Impossible

题意:

把初始的两堆卡片(一共两种颜色),转移为新的两堆(每堆只能是一种颜色),,并且在转移的过程中,新的两堆的个数相差不能大于一!

PS:

记忆化搜索,连续拿的卡片最多只能有三个是同一种颜色的!例如 11 10!

每次把连续拿两张卡片看为一个整体!

代码如下:

#include <cstdio>char a[1047], b[1047];int dp[1047][1047];int dfs(int x, int y){if(x==0 && y==0)//找到了{return 1;}if(dp[x][y]){return 0;}if(!dp[x][y]){dp[x][y] = 1;}if(x>=2 && a[x]!=a[x-1] && dfs(x-2,y))//每次拿不同的{printf("11");//第一堆 黑色return 1;}if(y>=2 && b[y]!=b[y-1] && dfs(x,y-2)){printf("22");return 1;}if(x>=1 && y>=1 && a[x]!=b[y] && dfs(x-1,y-1)){printf("12");return 1;}return 0;}int main(){int n;scanf("%d",&n);scanf("%s",a+1);scanf("%s",b+1);int flag = dfs(n,n);if(!flag){printf("Impossible\n");}else{printf("\n");//}}return 0;}/*400110110411001100*/

我们一直在旅行,一直在等待某个人可以成为我们旅途的伴侣,

URAL 1501. Sense of Beauty(记忆化搜索 dfs)

相关文章:

你感兴趣的文章:

标签云: