墙壁涂色(DP)
2024-10-08 18:37:59
蒜头君觉得白色的墙面好单调,他决定给房间的墙面涂上颜色。
他买了 3 种颜料分别是红、黄、蓝,然后把房间的墙壁竖直地划分成 n 个部分,蒜头希望每个相邻的部分颜色不能相同。
他想知道一共有多少种给房间上色的方案。
例如,当 n = 5 时,下面就是一种合法方案。
由于墙壁是一个环形,所以下面这个方案就是不合法的。
输入格式
一个整数 n,表示房间被划分成多少部分。(1 <=n<=50)
输出格式
一个整数,表示给墙壁涂色的合法方案数。
样例输入
4
样例输出
18
解题思路
设dp[i]为长度为i的方案数,然后找出 dp[n] 与 dp[n - 1] 和 dp[n - 2] 的关系。
考虑第 1 块和 n-1块颜色不一样的情况,现在第 n 块要和第 n-1和 1 都不一样,但是只有 3 种颜色,所以 n 只有一种颜色选择,这种情况方案数正好是 dp[n-1]。
考虑第 1 块和 n-1 块颜色一样的情况,第 n-2 块必然要和第 n-1 块不同,同时也就和第 1 块不同,前面 n-2 块方案数是 dp[n-2],第 n 块要和第 1 块和第 n-1块不同,有 2 种选择,所以这种情况方案数是 2∗dp[n−2]。
上面 2 种情况加起来就是总方案数。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <ctime>
const int INF=0x3f3f3f3f;
typedef long long LL;
const int mod=1e9+;
const double PI = acos(-);
const double eps =1e-;
#define Bug cout<<"---------------------"<<endl
const int maxn=1e5+;
using namespace std; LL dp[];//注意开long long int main()
{
int n;
scanf("%d",&n);
dp[]=; dp[]=; dp[]=;
for(int i=;i<=n;i++)
{
dp[i]=dp[i-]+*dp[i-];
}
printf("%lld\n",dp[n]);
return ;
}
-
最新文章
- Jquery AJAX ASP.NET IIS 跨域 超简单解决办法
- POJ 1654 Area(水题)
- 含大量行的订单创建时候creditlimit校验最耗时间
- java微信开发框架wechat4j入门教程
- NSS_09 gridpanel中的actioncolumn事件
- 244. Shortest Word Distance II
- jvm所占空间的配置
- C++通过域名获取IP地址的方法;调试通过!
- zabbix3.0.4 部署History
- java 反射与常用用法
- json字符串转成数组
- 使用element ui 日期选择器获取值后的格式问题
- “玲珑杯”ACM比赛 Round #4 B 	Best couple
- HashMap循环过程中删除元素发生ConcurrentModificationException的源码分析
- Ubuntu 16.04 安装Kinect V2驱动
- pip 提速方法
- 5、Qt Project之键盘数据监控
- Maven项目下servlet异常
- css学习_css书写规范
- Win32汇编环境搭建教程(MASM32 SDK)
热门文章
- Vmware 和 VisualSVN-Server端口冲突
- java学习之IO流(学习之旅,一)
- python中pandas数据分析基础3(数据索引、数据分组与分组运算、数据离散化、数据合并)
- python matplotlib绘图大全(散点图、柱状图、饼图、极坐标图、热量图、三维图以及热图)
- Asp.net禁用site.Mobile.Master
- 3 —— node —— 文件追加内容
- 【LeetCode】最小栈
- (转)linux shell 的here document 用法 (cat <;<; EOF)
- Android Studio 移动虚拟机
- AFNetworking实现表单(multipart)形式上传图片