首页 > ACM题库 > HDU-杭电 > Hdu 1683 Colour sequence-动态规划[解题报告] C++
2013
12-21

Hdu 1683 Colour sequence-动态规划[解题报告] C++

Colour sequence

问题描述 :

We have a pile of cards consisting of 100 cards that are coloured on both sides. There is a finite number of colours (at most 26). In addition there are special cards called jokers. Jokers have a joker sign on both sides, which can assume any of the possible colours. We consider here a one-player card game, in which the player is challenged to derive a given colour sequence from a given row of cards, following certain rules.

Before the actual beginning of the game a colour sequence S of length at most 100 (not containing a joker) is given. Furthermore a number of cards are chosen from the pile and are put in a row. The sides turned upwards form a row of colours. Now the aim for the player is to create the colour sequence S with the cards from the row in the following way. For each card in the row the player decides whether or not to turn it over. When the card is turned over, only the colour on the other side is visible. Jokers may be part of the row of cards.

These steps lead to the final sequence of colours formed by the visible side of the cards in the row. If the player has been able to turn the cards in such a way that the pre-given colour sequence S is contained (from left to right) in the final row of colours, the player wins. If not, he loses. In matching the pre-given colour sequence to the row, cards in the row may be skipped, as long as the relative order of the colours is preserved. A joker can assume any colour. For example, the colour sequence (red, blue, yellow) is contained in (green, joker, blue, red, yellow), and (blue, green, blue, green) is contained in (red, blue, joker, yellow, joker, blue, green, green).

Your job is to find out if the player can win, given the colour sequence S and the row of cards chosen from the pile. This means that the sequence of colours that are face up is known, and so are the colours on the other side of these cards.

输入:

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

One line describing the colour sequence S. This line contains a string of m (with 1 ≤ m ≤ 100) characters from the set {‘A’, ‘B’, …, ‘Z’}, denoting the colours. Different colours correspond to different characters. For example: "BGBG" denotes the sequence blue, green, blue, green.

Two lines, corresponding to the row of cards chosen from the pile. Each of these lines contains a string of k (1 ≤ k ≤ 100) characters from the set {‘A’, ‘B’, …, ‘Z’, ‘*’}. The character ‘*’ denotes a joker, which can play the role of any of the possible colours.

The string in the first line corresponds to the row of colours on the visible side of the cards. The string in the second line corresponds to the row of colours on the hidden side of the cards.

So for the ith card in the row, the first line gives the colour of the side turned upwards and the second line shows the colour of the side face down. Obviously the strings on both lines have the same length. Furthermore, a ‘*’ in one line (denoting a joker) always corresponds to a ‘*’ in the other line at the corresponding position.

输出:

For every test case in the input file, the output should contain one line. This line contains "win" if the colour sequence S can be achieved by the player by turning the right cards upside down, and "lose" if this is not the case.

样例输入:

3
RBY
B*RRB
G*BRY
BGBG
RZ*Y*PGG
AB*Y*BCB
BAPC
BUBCDAPVDAVVDLPF
VLDCUSPGLSGPPVDD

样例输出:

win
win
lose


题目大意:有一列扑克牌,每一张牌都有两面,每一面是一种颜色,有一种牌是王牌,可以当作任何颜色。

现在给你一个颜色序列,要求把翻动某些扑克牌,使得这个序列是扑克牌颜色序列的子序列。

解题报告:这题的序列长度是<=100的
我们可以用DP来做,dp[i][j]代表序列前i个和扑克牌前j个是否可以翻成子序列。

递推方程:
if(dp[i][j])dp[i][j+1]=true;//即如果前j个可以的话前j+1个肯定是可以的。
if(b[j][0]=='*'||b[j][0]==a[i]||b[j][1]==a[i]&&dp[i-1][j-1])dp[i][j]=true;//即如果当前的牌是王牌或者有一面可以和第i个颜色匹配,那么可以在前面的基础上加一个过来。

递推是O(1)的状态量是O(N*M)
总的复杂度是O(N*M)

#include<math.h> 
#include<stdio.h> 
#include<string.h> 
#include<vector> 
using namespace std; 
const int MAX=110; 
const double PI=acos(-1.0); 
const double EPS=1.0e-8; 
typedef __int64 lld; 
//typedef long long lld; 
    
bool dig(char x){return x>='0'&&x<='9';} 
int getval() 
{ 
    int ret=0,sign=1; 
    char c; 
    while(!dig(c=getchar())&&c!='-'); 
    if(c=='-')sign=-1; 
    else ret=c-'0'; 
    while(dig(c=getchar()))ret=ret*10+c-'0'; 
    return ret*sign; 
} 
int dblcmp(double x) 
{ 
    if(fabs(x)<EPS)return 0; 
    return x<0?-1:1; 
} 
char a[MAX];
char b[2][MAX];
bool dp[MAX][MAX];
int main() 
{ 
    int T;
    int n,m,i,j;
    scanf("%d",&T);
    while(T–) 
    { 
        scanf("%s%s%s",&a[1],&b[0][1],&b[1][1]);
        n=strlen(&a[1]);
        m=strlen(&b[0][1]);
          
        memset(dp,false,sizeof(dp));
  
        for(i=0;i<=m;i++)dp[0][i]=true;
  
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(dp[i][j-1])dp[i][j]=true;
  
                if(b[0][j]=='*'||b[0][j]==a[i]||b[1][j]==a[i])
                {
                    if(dp[i-1][j-1])dp[i][j]=true;
                }
            }
        }
  
        if(dp[n][m])puts("win");
        else puts("lose");
    } 
    return 0; 
} 

 


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. [email protected]

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。