网站优化怎么做分录,网站建设建议,网站建设方案总结,学校网站建设调查报告★ 输入文件#xff1a;nucle.in 输出文件#xff1a;nucle.out 简单对比 时间限制#xff1a;1 s 内存限制#xff1a;128 MB 【问题描述】 一个核电站有 N 个放核物质的坑#xff0c;坑排列在一条直线上。如果连续 M 个坑中放入核物质#xff0c;则会发生爆炸nucle.in 输出文件nucle.out 简单对比 时间限制1 s 内存限制128 MB 【问题描述】 一个核电站有 N 个放核物质的坑坑排列在一条直线上。如果连续 M 个坑中放入核物质则会发生爆炸于是在某些坑中可能不放核物质。 任务对于给定的 N 和 M 求不发生爆炸的放置核物质的方案总数。 【输入格式】 输入文件nucle.in只一行两个正整数 N M( 1N50 2 ≤ M ≤ 5) 【输出格式】 输出文件 (nucle.out) 只有一个正整数 S 表示方案总数。 【输入输出样例】 输入 nucle.in 4 3 输出 nucle.out 13 思路 若用f[i]储存在这个坑时的已经计算过的所有情况 对于一个坑有三种情况 1nm在这种情况下只有两种情况 放与不放。于是此时所有的情况就是2*f[i-1] 2nm 这种情况下也可以选择放与不放但是当放的时候若前n-1个已经放了物质则第n个不能放 于是所有的情况就是2*f[i-1]-1 3:nm 当选择不放的时候就是加上f[i-1]的所有情况 当选择放的时候要考虑若放上会爆炸的情况我们先想若放上之后不爆炸的情况就是f[i-1]再减去放上之后会爆炸的情况。那么放上之后会爆炸的情况是什么呢如果我们放上会爆炸那么i-m-1个一定没有放。所以放上会爆炸的情况就是f[i-m-1]. So这种情况下的所有情况就是2*f[i-1]-f[i-m-1] 1 #includecstdio2 using namespace std;3 int main()4 {5 freopen(nucle.in,r,stdin);6 freopen(nucle.out,w,stdout);7 long long f[50];8 int i,n,m;9 cinnm;
10 f[0]1;
11 for(i1;in;i)
12 {
13 if(im) f[i]2*f[i-1];
14 if(im) f[i]2*f[i-1]-1;
15 if(im) f[i]2*f[i-1]-f[i-m-1];
16 }
17 coutf[n]endl;
18 return 0;
19 } 转载于:https://www.cnblogs.com/zwfymqz/p/6558363.html
