专栏首页ACM算法日常乐乐的RPG难题(递推) - HDU 2045

乐乐的RPG难题(递推) - HDU 2045

Problem Description

人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即"可乐"),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题: 有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法. 以上就是著名的RPG难题. 如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成,(0<n<=50)。

Output

对于每个测试实例,请输出全部的满足要求的涂法,每个实例的输出占一行。

Sample Input

1
2

Sample Output

3
6

首先,看到这道题,我们肯定是去想找到它的规律,要不然无从下手。如果你没有想到递推找到规律也是挺难想的,那如果是递推应该是什么规律呢?

核心代码如下:

num[i]=num[i-1]+2*num[i-2];//num[i]代表有i个格对应的涂法

那么为什么如此呢?

首先我们要清楚我们的目的:找到所有种涂法。接下来我们以5个格的情况去举例

第一个格永远不受任何限制,可以取三种,这里以红色为例,那么如果只看前4个格,第四个格只可能为绿和蓝,在这种情况下,如果第4个取绿,第5个只能取蓝一种取法,此时有num[5]=num[4](即5=4+1的情况下的涂法与4个格涂法相同)

此时还没完,为什么呢?因为情况没有完全取完,第四格由于受第一格约束,不能取红。但实际5个格的话第4个格可以取红。

因此我们在考虑5=3+2,因为此时第一个格已经不能影响第四格了,由于第四个格在上一种情况中已经取绿与蓝了,因此只考虑取红即可。而此时第5个格可取绿与蓝。3格的每种涂法上4,5取红绿或红蓝,即2*num[3]。即num[5]=num[4]+2*num[3]。

那么此时取完了吗,当然,因为第3格在5=4+1情况下不受第一格限制,第2格在任何情况下均受第一格限制,因此,可以肯定所有合法的情况已经取完,且5=4+1,5=3+2情况下因为第4格取颜色不同,因此情况也不会有重复。即为所有涂法。

这样分析以后,我们也就清楚了为什么从4格以后递归,因为只有3格时,2,3格一定会受到第一格影响,情况也只有一种。

同理也可以给出m种颜色下的核心代码:

num[i]=(m-2)*num[i-1]+(m-1)*num[i-2];

代码如下:

#include
using namespace std;
int main()
{
    int n;
    long long num[55];
    num[1]=3;num[2]=6;num[3]=6;
    int i;
    for(i=4;i<=50;i++)
    {
        num[i]=num[i-1]+2*num[i-2];
    }
    while(cin>>n)
    {
        cout<<num[n]<<endl;
    }
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:逆风飞翔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一次讲透次短路及条数问题,详细探讨dijkstra算法的本质

    继续学习次短路~ hdu 3191 How Many Paths Are There

    ACM算法日常
  • 最多因子数(DFS+数论+剪枝)- CodeVS 1032

    数学家们喜欢各种类型的有奇怪特性的数。例如,他们认为945是一个有趣的数,因为它是第一个所有约数之和大于本身的奇数。

    ACM算法日常
  • leetcode 7 | 反转整数(简单题)

    假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

    ACM算法日常
  • 【leetcode刷题】T45-丑数

    Write a program to check whether a given number is an ugly number.

    木又AI帮
  • leetcode 31 Next Permutation

    @坤的
  • 蓝桥杯之全排列函数next_permutation()运用

    在蓝桥杯的题目中大多数都可以运用到全排列函数 充分运用可以节省很多的时间。话不多说来刷题

    用户4492257
  • Leetcode_342_Power of Four

    http://blog.csdn.net/pistolove/article/details/52198328

    bear_fish
  • 计蒜客蓝桥杯模拟赛 九宫格

    题目 将数字 1…9 填入一个3×3 的九宫格中,使得格子中每一横行和的值全部相等,每一竖列和的值全部相等。请你计算有多少种填数字的方案。

    用户4492257
  • 丑数

    一份执着✘
  • LeetCode | 2 的幂

    这题也是比较容易的一题,前提是找到规律即可。如果从 10 进制的角度观察 2 的幂次方,可能并不容易发现规律,那么可以从 2 进制的角度进行观察...

    码农UP2U

扫码关注云+社区

领取腾讯云代金券