ACM_递推题目系列之一涂色问题(递推dp)
2024-08-28 07:59:06
Problem Description:
有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.
Input:
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成,(0<n<=50)。
Output:
对于每个测试实例,请输出全部的满足要求的涂法,每个实例的输出占一行。
Sample Input:
3
8
Sample Output:
6
258
解题思路:找规律递推题。首先易知f(1)=3;f(2)=6;f(3)=6;f(4)=18;现在考虑n>3的情况,①若第n-1个格子和第1个格子不同,则为f(n-1)*1;②第n-1个格子和第1个格子相同,则第n-2个格子和第一个格子必然不同,此时为f(n-2)再乘第n-1个格子的颜色数,很显然第n-1个格子可以是第一个格子(即第n-2个格子)的颜色外的另外两种,这样为2*f(n-2);因此总的情况为f(n)=f(n-1)+2*f(n-2);
AC代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
long long p[]={,,,};
for(int i=;i<;i++)
p[i]=p[i-]+p[i-]*;
while(cin>>n)
cout<<p[n]<<endl;
return ;
}
最新文章
- 根据用户IP获得所在城市
- LinkedList方法总结 ListIterator和Iterator的区别
- 用Quartz进行作业调度(转)
- ExtJS参考手册
- SSH三大框架合辑的搭建步骤
- Demo_敌军坦克生成,坦克移动(可以拓展发射子弹,敌军消失获取分数或者添加动画,声音功能)
- Java 模拟队列(一般队列、双端队列、优先级队列)
- 分享一款CSS框架
- T-SQL语法基础
- ASP.NET Core 2.0 MVC项目实战
- Oracle导出表数据与导入表数据dmp,以及导入导出时候常见错误
- python绘图之seaborn 笔记
- 初识Docker和安装
- 数据库实例: STOREBOOK >; 表空间 >; 编辑 表空间: SYSTEM
- Set集合遍历方式
- 谁动了我的Mac ??
- orale存储技术
- android应用中插入admob广告
- JavaScript世界万物诞生记
- 将本地项目上传到git远程库(初始化)
热门文章
- HDU 4416 (后缀自动机)
- P2910 [USACO08OPEN]寻宝之路Clear And Present Danger 洛谷
- k-d树及八叉树
- CentOS 6.9正式版下载
- myEclipse怎样将程序部署到tomcat(附录MyEclipse调试快捷键)
- JS 获取form表单的所有数据
- PromiseKit入门
- Maven手工安装jar包到本地仓库
- RK3288][Android6.0] 调试笔记 --- 关闭按键音后无法录音问题【转】
- linux进程间通信——netlink【转】