首页 > ACM题库 > HDU-杭电 > hdu 2526 浪漫手机-动态规划-[解题报告]C++
2014
02-09

hdu 2526 浪漫手机-动态规划-[解题报告]C++

浪漫手机

问题描述 :

最近,WisKey迷上了手机铃声,但是他对音律不是很懂,所以他想着能否用计算机来随机生成铃声。当WisKey写好程序后,发现生成出来的根本不是铃声,而是噪声!
之后WisKey查阅了一些乐谱发现,其实很多铃声是以某种规律变化的,这里为了简化这个难题,他以连续3个音符来判断下个音符。
如有模式

在给定第一行乐谱的情况下,按模式将产生如下乐谱图形:

我们用0表示白色格子,用1表示黑色格子。
对于没有连续3个格子的边缘(即没有左边格子或右边格子),我们直接用白色格子代替缺少的那一个格子。

输入:

第一行有一个整数T,代表有T组数据。
每组数据有一个整数M,表示要输出M行乐谱。接着有8行模式串,左边是音符模式,右边是下一个音符。最后一行是第一行乐谱。

输出:

第一行有一个整数T,代表有T组数据。
每组数据有一个整数M,表示要输出M行乐谱。接着有8行模式串,左边是音符模式,右边是下一个音符。最后一行是第一行乐谱。

样例输入:

1
16
111 1
110 1
101 1
100 1
011 1
010 0
001 1
000 0
0000000000000001000000000000000

样例输出:

0000000000000001000000000000000
0000000000000010100000000000000
0000000000000101010000000000000
0000000000001010101000000000000
0000000000010101010100000000000
0000000000101010101010000000000
0000000001010101010101000000000
0000000010101010101010100000000
0000000101010101010101010000000
0000001010101010101010101000000
0000010101010101010101010100000
0000101010101010101010101010000
0001010101010101010101010101000
0010101010101010101010101010100
0101010101010101010101010101010
1010101010101010101010101010101

2011-12-20 08:09:43

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2526

题意:中文。直接模拟。

代码:

# include <stdio.h>


int dp[1010][210] ;
int flag[200], m ;
char str[210] ;


int get(int a, int b, int c)
{
    return flag[a*100+b*10+c] ;
}


void output()
{
    int i, j, len = 0 ;
    for (i = 0 ; str[i]  ;i++)
    {
        dp[0][i] = str[i] - '0' ;
        len++ ;
    }
    for (i = 1 ; i < m ; i++)
    {
        dp[i][0] = get (0, dp[i-1][0], dp[i-1][1]) ;
        dp[i][len-1] = get(dp[i-1][len-2], dp[i-1][len-1], 0) ;
        for (j = 1 ; j < len-1 ; j++)
            dp[i][j] = get(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) ;
    }
    for (i = 0 ; i < m ; i++)
    {
        for (j = 0 ; j < len ; j++)
            printf ("%d", dp[i][j]) ;
        printf ("\n") ;
    }
}
int main ()
{
    int T, i, a, b ;
    scanf ("%d%*c", &T) ;
    while (T--)
    {
        scanf ("%d%*c", &m) ;
        for (i = 0 ; i < 8 ; i++)
        {
            scanf ("%d %d%*c", &a, &b) ;
            flag[a] = b ;
        }
        scanf ("%s%*c", str) ;
        output () ;
    }
    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/06/2315278.html


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的