hd acm2045
LELE的RPG难题
析:
假设有N个方格时的涂法是F[N]种。当前边n-1个方格成立时,再加第n种颜色无影响,此时有F[N-1]种涂法,当n-1个方格违法时,即有两个相邻的格子颜色相同,则有n-2个颜色合法,即F[N-2],第N种颜色有两种,此时2*F[N-1];继续分析n-3,发现要么是与前边情况重复,要么不存在这种情况。综上,F[N]=F[N-1]+2*F[N-2]。
代码:
#include <stdio.h>
#include <stdlib.h>
int main() //大数运算的套路。
{
int way[51][50]={0};
int n,i,j;
way[0][1]=3;
way[1][1]=3;
way[2][1]=6;
way[3][1]=6;
for(i=4;i<51;i++){
for(j=1;j<50;j++){
way[i][j]+=way[i-1][j]+2*way[i-2][j];
way[i][j+1]+=way[i][j]/10000;
way[i][j]%=10000;
}
}
while(scanf("%d",&n)!=EOF){
j=49;
while(!way[n][j--]);
printf("%d",way[n][j+1]);
for(;j>0;j--){
printf("%04d",way[n][j]);
}
printf("\n");
}
return 0;
}
最新文章
- tomcat 设置根目录访问
- Redis快速入门
- CMOS and BIOS
- CALayer加阴影后动画卡的处理办法
- SQL rank() 用法
- uva 1400 - ";Ray, Pass me the dishes!";
- leetcode面试准备:Divide Two Integers
- lua的学习
- Codeforces Round #270(利用prim算法)
- JAVA面试精选
- iOS 开发之 protocol Buffer 数据交换
- 【Python3爬虫】12306爬虫
- linux awk 常见字符串处理
- Charles for MAC配置与使用
- BZOJ1070[SCOI2007]修车——最小费用最大流
- ssh连接docker镜像ubuntu与debian
- Spring MVC 学习笔记11 —— 后端返回json格式数据
- Java URLEncoder URLDecoder
- 洛谷P3402 【模板】可持久化并查集 [主席树,并查集]
- python3-开发进阶Flask的基础
热门文章
- .NET CORE 2.0小白笔记(五):配置的热更新、配置的框架设计
- kafka eagle 使用教程
- nexus5刷机
- 搭建redis集群遇到的坑
- Apache配置压缩优化时报错——undefined symbol: inflateEnd
- 文本信息检索——布尔模型和TF-IDF模型
- HDU 5273 区间DP
- wireshark:Couldn&#39;t run /usr/bin/dumpcap in child process: Permission denied
- 【v2.x OGE教程 11】 动画编辑器帮助文档
- GUN C中的错误报告