UVA 580 Critical Mass

题目大意：U代表危险物品铀，L代表安全物品铅，当U连续数目>=3时，为危险情况。输入数字N代表有四个箱子，每个箱子可以存放U或者L，求危险情况种数。

                  （题意很麻烦，谁让是人家外国做的，唉~~~）

解题策略：网上有DP解的动态递推公式，还有一个策略是逆向考虑，通过解出安全的情况数，总情况数-安全情况数=危险情况数。

                  总情况数为2^N种（组合排列），安全情况数满 足add[i] = add[i-1] + add[i-2] + add[i-3]，然后循环预处理危险情况，对应输出即可。

 

/*
    UVA 580 Critical Mass
    AC by J.Dark
    ON 2013/3/1
    Time 0.008s
*/
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 500;
int main(){
    long long danger[maxn], add[maxn];
    add[3] = 7;
    add[4] = 13;
    add[5] = 24;
    for(int i=6; i<maxn; i++){
        add[i] = add[i-1] + add[i-2] + add[i-3]; 
    }
    for(int i=3; i<maxn; i++){
        danger[i] = (int)pow(2.0, i*1.0) - add[i];
    }
    
    int N;
    while( (cin >> N) && (N) )
    {
       cout << danger[N] << endl;
    }
    //system("pause");
    return 0;
}