A36051. 核电站
填空题
中等
知识点
题目描述
核电站
题目描述
一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数
输入
只一行，两个正整数N，M( 1 < N < 50，2 ≤ M ≤ 5 )
输出
一个正整数S，表示方案总数。
样例输入
4 3
样例输出
13
参考答案
#include<stdio.h>
int main()
{
int m,n;
int i;
long long int DP[60];//DP中贮存的是方案数目，数组下标是位置数
while(scanf("%d %d",&n,&m)!=EOF){
DP[0] = 1;//初始状态
for(i = 1 ; i <= n; i++)
{
if(i < m)
DP[i] = DP[i - 1]*2;//前m-1个坑中有两种选择：放炸弹或者不放，所以方案数 = 前一步的方案数*2
else if(i == m)
DP[i] = DP[i - 1]*2 - 1;//此处排除掉前m个全部放炸弹的这种情况。
else
DP[i] = DP[i-1]*2-DP[i-m-1];/*
此时依旧有两种方案放或者不放，总的方案数为DP[i-1]*2，而减去的为连续出现m个的可能情况；
当i>m+1时可以将连续的m个炸弹看做一个炸弹，但是此时这个炸弹是必须存在的；
所以当i == m+1时方案数为DP[0]，（即记录初始状态为）之后的状态类似i<m时。
*/
}
printf("%lld\n",DP[n]);}
return 0;
}答案解析
动态规划（DP）个人现在的理解为：通过数组的形式记录所求状态，对一类可以进行状态累积的问题，通过记录其变化而求解。主要是对状态转移方程的求出。此题的状态转移方程为：
dp[i] = dp[i-1]*2;(i < m)
dp[i] = dp[i - 1]*2 - 1;(i = m)
dp[i] = dp[i-1]*2 - dp[i-m-1];(i > m)
上一题
下一题