poj 1953 World Cup Noise (dp)
2024-10-07 00:38:15
World Cup Noise
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 16774 | Accepted: 8243 |
Description
Background
"KO-RE-A, KO-RE-A" shout 54.000 happy football fans after their team has reached the semifinals of the FIFA World Cup in their home country. But although their excitement is real, the Korean people are still very organized by nature. For example, they have organized huge trumpets (that sound like blowing a ship's horn) to support their team playing on the field. The fans want to keep the level of noise constant throughout the match.
The trumpets are operated by compressed gas. However, if you blow the trumpet for 2 seconds without stopping it will break. So when the trumpet makes noise, everything is okay, but in a pause of the trumpet,the fans must chant "KO-RE-A"!
Before the match, a group of fans gathers and decides on a chanting pattern. The pattern is a sequence of 0's and 1's which is interpreted in the following way: If the pattern shows a 1, the trumpet is blown. If it shows a 0, the fans chant "KO-RE-A". To ensure that the trumpet will not break, the pattern is not allowed to have two consecutive 1's in it.
Problem
Given a positive integer n, determine the number of different chanting patterns of this length, i.e., determine the number of n-bit sequences that contain no adjacent 1's. For example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are acceptable while 011, 110, 111 are not).
"KO-RE-A, KO-RE-A" shout 54.000 happy football fans after their team has reached the semifinals of the FIFA World Cup in their home country. But although their excitement is real, the Korean people are still very organized by nature. For example, they have organized huge trumpets (that sound like blowing a ship's horn) to support their team playing on the field. The fans want to keep the level of noise constant throughout the match.
The trumpets are operated by compressed gas. However, if you blow the trumpet for 2 seconds without stopping it will break. So when the trumpet makes noise, everything is okay, but in a pause of the trumpet,the fans must chant "KO-RE-A"!
Before the match, a group of fans gathers and decides on a chanting pattern. The pattern is a sequence of 0's and 1's which is interpreted in the following way: If the pattern shows a 1, the trumpet is blown. If it shows a 0, the fans chant "KO-RE-A". To ensure that the trumpet will not break, the pattern is not allowed to have two consecutive 1's in it.
Problem
Given a positive integer n, determine the number of different chanting patterns of this length, i.e., determine the number of n-bit sequences that contain no adjacent 1's. For example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are acceptable while 011, 110, 111 are not).
Input
The first line contains the number of scenarios.
For each scenario, you are given a single positive integer less than 45 on a line by itself.
For each scenario, you are given a single positive integer less than 45 on a line by itself.
Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the number of n-bit sequences which have no adjacent 1's. Terminate the output for the scenario with a blank line.
Sample Input
2
3
1
Sample Output
Scenario #1:
5 Scenario #2:
2
分析:result[i]存储 i位二进制数中没有相邻的1的个数。计算result[i],如果在result[i-1]中的各个数后加0,则都满足条件,如果在result[i-1]中的各个数后加1,要满足条件则result[i-1]中的数的最后一位必须是0,即是result[i-2]中各个数加0后的结果。所以
result[i] = result[i - 1] + result[i - 2]
其中result[1] 等于2,result[2]等于3,然后就是个斐波那契数列。
Java AC 代码
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testNum = sc.nextInt();
int[] result;
for(int i = 1; i <= testNum; i++) {
int bitNum = sc.nextInt();
result = new int[bitNum + 1];
if(bitNum == 1) {
System.out.println("Scenario #" + i + ":");
System.out.println(2);
System.out.println("");
continue;
}
result[1] = 2;
result[2] = 3;
for(int j = 3; j <= bitNum; j++) {
result[j] = result[j - 1] + result[j - 2];
}
System.out.println("Scenario #" + i + ":");
System.out.println(result[bitNum]);
System.out.println("");
}
}
}
最新文章
- zabbix完整安装
- 使用 CSS &; jQuery 制作一款漂亮的多彩时钟
- Win10 利用安装盘启用 .NET Framework 3.5
- 注册表法修改IE8安全级别的方法
- js html5推送 实例
- look
- 购买vps创建账号后无法登录ftp
- Oracle的参数文件
- 微信浏览器如何禁止iPhone手机上下滑动网页
- Codeforces Round #250 (Div. 1) D. The Child and Sequence (线段树)
- QTreeView只显示指定驱动器及其目录,隐藏所有兄弟节点
- Android 常用UI控件之TabHost(1)TabHost的两种布局方式
- CSS 实现流布局以及多列混合布局
- ALSA和Pulseaudio
- Swift的基础之UILabel控件
- 最新App Store审核10大被拒理由
- Tomcat中server.xml配置详解(2)
- Springboot 允许跨域访问
- 将 django部署到 heroku上
- MD5解密