【题目描述】

一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续３个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。现在，请你计算：对于给定的N，求不发生爆炸的放置核物质的方案总数。

【输入描述】

输入文件只有多行，每行对应一个正整数N＜＝4０；

【输出描述】

输出文件有多行，每行只有一个正整数，表示方案总数

【样例输入】

1  2  3  4  10

【样例输出】

2  4  7  13  504

【思路】

先求出N=1，2，3时的方案数。dp[i]=dp[i-1]+dp[i-2]+dp[i-3]。i从4开始，如果第i个坑不放，则第1到第i-1个坑可以在符合题意的情况下

随意放，即+dp[i-1]；如果第i个坑放，当第i-1个坑不放时，第1到第i-2个坑可以在符合题意的情况下随意放，即+dp[i-2]，当第i-1个坑放，第

i-2个坑不放（此时必须不放，因为不可能连续三个坑同时放）时，第1到i-3个坑可以在符合题意的情况下随意放，即+dp[i-3]，这就是dp[i]的所有情况了

（因为第i个，i-1个，i-2个不可能同时放）。

【参考答案】

#include <iostream>  using namespace std;  int main() {  	long long dp[50]= {0};  	dp[1]=2;  	dp[2]=4;  	dp[3]=7;  	for(int i=4; i<41; i++)  		dp[i]=dp[i-1]+dp[i-2]+dp[i-3];  	int n;  	while(cin>>n)cout<<dp[n]<<endl;  }