动态规划练习 4

题目：World Cup Noise (POJ 1953)

链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1953

#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
    int scenarios;

    cin >> scenarios;

    for (int i = 1; i <= scenarios; ++i)
    {
        int n;

        cin >> n;

        if (n >= 1 && n < 45)
        {
            int last1[45];
            int last0[45];

            last1[1] = 1;
            last0[1] = 1;

            for (int j = 2; j <= n; ++j)
            {
                last1[j] = last0[j - 1];
                last0[j] = last0[j - 1] + last1[j - 1];
            }

            cout << "Scenario #" << i << ":" << endl;
            cout << last0[n] + last1[n] << endl << endl;
        }
    }

    return 0;
}