poj1953

maksyuki 发表于 oj 分类，标签: DP-线性DP

03 3月 2017

World Cup Noise
"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.

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

Sample Output

Scenario #1:

Scenario #2:

Source

TUD Programming Contest 2002, Darmstadt, Germany

题目类型：线性DP

算法分析：dp[0][i]表示以0结尾的长度为i的串的方案数，dp[1][i]表示以1结尾的长度为i的串的方案数，初始化dp[0][1] = dp[1][1] = 1，状态转移方程为dp[0][i] = dp[0][i-1] + dp[1][i-1]，dp[1][i] = dp[0][i-1]，最后查表输出dp[0][n] + dp[1][n]即可

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/3/3 20:30:09
last modified  :2017/3/3 20:38:03
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CPPFF ifstream cin ("in")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int dp[2][66];

int main()
{
    //CFF;
    //CPPFF;
    int id = 1;
    dp[0][1] = dp[1][1] = 1;
    for(int i = 2; i <= 50; i++)
    {
        dp[0][i] = dp[0][i-1] + dp[1][i-1];
        dp[1][i] = dp[0][i-1];
    }

    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        printf("Scenario #%d:\n", id++);
        printf("%d\n\n", dp[0][n] + dp[1][n]);
    }
    return 0;
}

/**************************************************

filename :e.cpp

author :maksyuki

created time :2017/3/3 20:30:09

last modified :2017/3/3 20:38:03

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CPPFF ifstream cin ("in")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int dp[2][66];

int main()

{

//CFF;

//CPPFF;

int id = 1;

dp[0][1] = dp[1][1] = 1;

for(int i = 2; i <= 50; i++)

{

dp[0][i] = dp[0][i-1] + dp[1][i-1];

dp[1][i] = dp[0][i-1];

}

int t;

scanf("%d", &t);

while(t--)

{

int n;

scanf("%d", &n);

printf("Scenario #%d:\n", id++);

printf("%d\n\n", dp[0][n] + dp[1][n]);

}

return 0;

}

poj1664

poj2181

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

poj1953

分类目录

标签云

书签

近期评论