时间限制: 1 Sec 内存限制: 128 MB
题目描述
小蔡决定在小头家门口安放炸弹！！
小头家门口有n个连续的格子排成一行，对于每个格子，小蔡可以决定放一颗炸弹或者不放。为了防止小头被炸死，**小蔡不会在连续3个格子都放上炸弹。**小蔡想知道一共有多少安放炸弹的方案(可以一个也不放)。
由于方案数可能很多，所以你只需要方案个数mod 55555就可以了。
输入
一个正整数，即n（n≤1000）
输出
仅包含一个整数，即答案
样例输入
4
样例输出
13
提示
对于样例1的解释，一共有4个格子，每个格子可以选择放或者不放，因此根据乘法原理共有222*2=16种方案，其中在（1，2，3）上放炸弹是不合法的，会炸死小头。同样（2，3，4）和（1，2，3，4）也都不合法，所以一共有16-3=13种方案，13 mod 55555=13，因此答案为13
这道题说起来算是很水的，有的同学直接找规律就做出来了，啥规律？
格子数目方案数122437413524644……
聪明的你一定发现规律了吧，也就是从第4项开始，每个的方案数==它前面三个的方案数的和。
俗话说，“不管白猫黑猫，抓到老鼠就是好猫”。
但是，如果你是出题人，怎么会让学生去生硬地找规律呢？所以，我们还得谈谈这道题的套路——正解是动规，所以要找状态转移方程。
明确状态：
dp[i][j]表示的是第i个格子连续放了j个炸弹，j只能取0,1,2。
为啥要选择这样来表示呢？题目加粗部分。
选择：
两个——放或不放炸弹
base case
第一个格子连续放0个，dp[1][0]=1;
第一个格子连续放1个，dp[1][0]=1;//比较简单的吧
第二个格子连续放0个，dp[2][0]=2;//1,0 and 0,0
第二个格子连续放1个，dp[2][1]=1;//0,1
第二个格子连续放2个，dp[2][2]=1;//1,1
目标存放
ans==dp[n][0]+dp[n][1]+dp[n][2]
算法方程
dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
dp[i][1]=dp[i-1][0]
dp[i][2]=dp[i-1][1]
分析结束
注意要mod55555哦。
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 1e5+10
using namespace std;
int dp[1010][3];
int main()
{
int n;
scanf("%d",&n);
dp[1][0]=1;
dp[1][1]=1;
dp[2][0]=2;
dp[2][1]=1;
dp[2][2]=1;
for(int i=3;i<=n;i++)
{
dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
dp[i][0]%=55555;
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][1];
}
printf("%d",(dp[n][0]+dp[n][1]+dp[n][2])%55555);
return 0;
}
如果有什么错误，欢迎批评指正。