开发者社区> kissjz> 正文

算法学习之路|墙壁涂色

简介: 蒜头君觉得白色的墙面好单调,他决定给房间的墙面涂上颜色。他买了 33 种颜料分别是红、黄、蓝,然后把房间的墙壁竖直地划分成 nn 个部分,蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。
+关注继续查看

题目大意
蒜头君觉得白色的墙面好单调,他决定给房间的墙面涂上颜色。他买了 33 种颜料分别是红、黄、蓝,然后把房间的墙壁竖直地划分成 nn 个部分,蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。

例如,当 n=5n=5 时,下面就是一种合法方案。
image

由于墙壁是一个环形,所以下面这个方案就是不合法的。

image

输入格式
一个整数 nn,表示房间被划分成多少部分。(1≤n≤501≤n≤50)

输出格式
一个整数,表示给墙壁涂色的合法方案数。

样例输入
4
样例输出
18
dp[n]表示n涂色的合法方案数。(即每个相邻颜色不相同且n和第一个不相同)

1.当n-1和1处颜色不同时,那么n处只能有一种选择。那么这种情况时,dp[n]=dp[n-1]

(n-1个合法方案中每一种都满足情况1)

2.当n-1和1处颜色相同时,那么n处有两种选择。

(这时,n-1与1颜色相同,这种情况共dp[n-2]种:n-2种合法方案后,面再加一个与1处的相同颜色n-1,就是情况2的方案数)

那么,满足一般条件n>3的状态转移方程为:

dp[i]=2*dp[i-2]+dp[i-1];

存在不满足一般条件的特殊情况:(手算即可)

dp[0]=3;

dp[1]=6;

dp[2]=6;


#include<iostream>
#define ll long long//暴力的结果一般很大
using namespace std;

int main(){
    ll dp[51];
    dp[1]=3;
    dp[2]=6;
    dp[3]=6;
    int n;
    cin>>n;
    for(int i=4;i<=n;i++){
        dp[i]=2*dp[i-2]+dp[i-1];
    }
    cout<<dp[n];
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
网络安全与机器学习(一):网络安全中的机器学习算法
网络安全遇见机器学习,会摩擦出怎样的火花呢?
3172 0
算法学习之路|数字黑洞
给定任一个各位数字不完全相同的4位正整数,如果我们先把4个数字按非递增排序,再按非递减排序,然后用第1个数字减第2个数字,将得到一个新的数字。一直重复这样做,我们很快会停在有“数字黑洞”之称的6174,这个神奇的数字也叫Kaprekar常数。
989 0
算法学习之路|打印沙漏
本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”,要求按下列格式打印
1281 0
算法学习之路|A除以B
本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。
839 0
算法笔试模拟题精解之“能量半径”
题目的含义就是找到距离原点最近的第k个点,并求它的半径。这个题的关键在于排序算法。使用最简单的冒泡排序,时间复杂度O(n^2);使用快速排序等好一点的排序算法,时间复杂度O(nlog(n));也可以使用java中Arrays类中的sort函数。
445 0
算法笔试模拟题精解之“变换的密钥”
根据题意,只要根据给出的初始关系,计算出对于每个字母可以变成的字母,就可以直接判断s1能不能转化成s2了。对于求幂操作有可以加快计算的方法,叫做矩阵快速幂。这里用求数的次幂举例。
336 0
算法题——投篮比赛获胜概率问题
问题描述: 甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。
797 0
算法学习之路|卖个萌
萌萌哒表情符号通常由“手”、“眼”、“口”三个主要部分组成。简单起见,我们假设一个表情符号是按下列格式输出的:
893 0
+关注
kissjz
Keep It Simple , Stupid. 独立博客:白水东城(www.baishuidongcheng.com)
246
文章
44
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载