【问题描述】
一个核电站有 N 个放核物质的坑，坑排列在一条直线上。如果连续 M 个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。
任务：对于给定的 N 和 M ，求不发生爆炸的放置核物质的方案总数。
【输入格式】
输入文件（nucle.in）只一行，两个正整数 N ， M( 1<N<50 ， 2 ≤ M ≤ 5)
【输出格式】
输出文件 (nucle.out) 只有一个正整数 S ，表示方案总数。
【输入输出样例】
输入：
nucle.in
4 3
输出：
nucle.out
13
本题是数值递推，主要是方程难写，我很水，想了两天，终于推出来了。i表示有多少个坑，j表示最多的炸弹连续数，方程为q[i][j]=(q[i-1][j]<<1)-q[i-j-1][j],我就不解释了，主要是一定要初始化前六位！！ 原程：C++语言: made by PaulInsider!
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,m,ji=0,answer=0;
long long q[51][6]={{},{0,0,2,2,2,2},{0,0,3,4,4,4},{0,0,5,7,8,8},{0,0,8,13,15,16},{0,0,13,24,29,31},{0,0,21,44,56,61},{0,0,34,81,108,120},{0,0,55,149,208,236}};
int main()
{
freopen ("nucle.in","r",stdin);
freopen ("nucle.out","w",stdout);
scanf("%d%d",&n,&m);
if (n<=8)
{
cout<<q[n][m];
return 0;
}
else
{
for (int i=9;i<=n;i++)
{
for (int j=2;j<=m;j++)
{
q[i][j]=(q[i-1][j]<<1)-q[i-j-1][j];
}
}
cout<<q[n][m];
}
return 0;
}
|
