核电站递推c++
题目大意:一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。对于给定的N和M,求不发生爆炸的放置核物质的方案数。样例输入:4 3//N和M;样例输出:13//方案数;样例解释:自己算。数据范围:目测tyvj无范围。。。还是rqnoj靠谱些。。。1< N <50,2<= M <=5;解题思路:数学?不会
题目大意:
一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。对于给定的N和M,求不发生爆炸的放置核物质的方案数。
样例输入:
4 3//N和M;
样例输出:
13//方案数;
样例解释:
自己算。
数据范围:
目测tyvj无范围。。。还是rqnoj靠谱些。。。
1< N <50,2<= M <=5;
解题思路:
数学?
不会做。
神犇自己加油。
考虑动态规划。
当i < m时,f[i]=2*f[i-1];
当i = m时,f[i]=2*f[i-1]-1;
当i > m时,f[i]=2*f[i-1]-f[i-m-1];
边界f[0]=1,随便写写,二十行结束。
说一说i > m的情况,f[i-1]*2的结果减去第i-m+1个到第i个全放的结果(不合法)即为答案。第i-m+1个到第i个全放的方案数等于第i-m个不放的方案数,注意不是f[i-m]的方案数,因为如果第i-m个位置放了,向后推就会发现第i-1个放物质就会爆炸,与我们所求的不符。最后考虑第i-m个不放的方案数=f[i-m-1].因为第i-m位置“不放”状态确定,求出前i-m-1个的合法方案数即可。
代码
题目大意:
一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。对于给定的N和M,求不发生爆炸的放置核物质的方案数。
样例输入:
4 3//N和M;
样例输出:
13//方案数;
样例解释:
自己算。
数据范围:
目测tyvj无范围。。。还是rqnoj靠谱些。。。
1< N <50,2<= M <=5;
解题思路:
数学?
不会做。
神犇自己加油。
考虑动态规划。
当i < m时,f[i]=2*f[i-1];
当i = m时,f[i]=2*f[i-1]-1;
当i > m时,f[i]=2*f[i-1]-f[i-m-1];
边界f[0]=1,随便写写,二十行结束。
说一说i > m的情况,f[i-1]*2的结果减去第i-m+1个到第i个全放的结果(不合法)即为答案。第i-m+1个到第i个全放的方案数等于第i-m个不放的方案数,注意不是f[i-m]的方案数,因为如果第i-m个位置放了,向后推就会发现第i-1个放物质就会爆炸,与我们所求的不符。最后考虑第i-m个不放的方案数=f[i-m-1].因为第i-m位置“不放”状态确定,求出前i-m-1个的合法方案数即可。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long f[55];
int main(){
int n,m;
cin>>n>>m;
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;i++){
if(i<m)
f[i]=2*f[i-1];
else if(i==m)
f[i]=2*f[i-1]-1;
else
f[i]=2*f[i-1]-f[i-m-1];
}
cout<<f[n];
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
这题的思路真是可以可以。
————————————————
版权声明:本文为CSDN博主「dugudashen」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/dugudashen/article/details/5182899
这题的思路真是可以可以。
————————————————
版权声明:本文为CSDN博主「dugudashen」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/dugudashen/article/details/51828995
更多推荐
所有评论(0)