ZSTUOJ刷题⑧:Problem G.--铺地砖
2024-10-22 04:53:34
Problem G: 铺地砖
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 6461 Solved: 2592
Description
元旦过去了,新年大酬宾活动也已经告一段落了。陈盖历望着堆在仓库的瓷砖,很无聊的他把这些瓷砖裁成很多1X1 1X2 1X3的小瓷砖,然后他把这些小瓷砖排在地上画的一个1*n的长方形里。问铺满这个长方形共有多少种方法?
Input
首先输入一个整数T,表示有T组测试数据 然后是T行,每行输入1个正整数n(n<=50)
Output
对于每个n输出铺的方法种数
Sample Input
3
1
2
3
Sample Output
1
2
4
这题要注意1+2和2+1是两种方法,不要像我一样傻乎乎┭┮﹏┭┮
这题通过枚举法可以发现从第四项开始,其值为前三项之和,可以使用递归,但递归时间效率太低,可以采用如下的数组的方法。
代码如下:
#include<bits/stdc++.h>
using namespace std; int main(){
int t;
while(cin>>t){
while(t--){
int a[51]={1,2,4};
int n;cin>>n;
for(int i=3;i<n;i++){
a[i]=a[i-1]+a[i-2]+a[i-3];
}
cout<<a[n-1]<<endl;
}
} return 0;
}
最新文章
- Python中获取当前日期的格式
- 使用CodeDom动态生成类型
- Ubuntu下tftp服务器的搭建
- 基于php使用memcache存储session的详解(转)
- Java多线程---同步与锁
- HTML5新增Canvas标签及对应属性、API详解(基础一)
- Mac下好用的取色器 Sip
- iOS的一些坑
- part 5 Two way databinding in AngularJS
- Oracle 取上周一到周末日期的查询语句
- IOS开发之路三(XML解析之GDataXML的使用)
- jqGrid使用整理
- Matlab: 路径的操作
- pytorch_SRU(Simple Recurrent Unit)
- android中进度条的实现
- GRPC单向/双向流
- vue 项目 使用sass
- 20175310 迭代和JDB
- Redis 主从复制, 读写分离
- Swift3 重写一个带占位符的textView