Tyvj P3119 核电站问题 动态规划

P3119 核电站问题
时间: 1000ms / 空间: 65536KiB / Java类名: Main

描述

  一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。 
  任务:对于给定的N和M,求不发生爆炸的放置核物质的方案总数

输入格式

  输入文件只一行,两个正整数N,M( 1

输出格式

  输出文件只有一个正整数S,表示方案总数。

测试样例1

输入

4 3

输出

13

题解:

动态规划
f[i][j]为到第i个,放了j个爆炸物的方案数。
数学方法不行QAQ
 #include<bits/stdc++.h>
using namespace std;
#define LL long long
LL f[][];
int main()
{
freopen("nucle.in","r",stdin);
freopen("nucle.out","w",stdout);
LL ans,n,m,i,j,k;
scanf("%lld %lld",&n,&m);
memset(f,,sizeof(f));//f[i][j]为到第i个,放了j个爆炸物的方案数.
f[][]=f[][]=;
for(i=;i<=n;i++)
{
for(j=;j<m;j++)f[i][]+=f[i-][j];
for(j=;j<m;j++)f[i][j]+=f[i-][j-];
}
ans=;
for(i=;i<m;i++)ans+=f[n][i];
printf("%lld",ans);
/*错误的数学方法
for(i=1;i<=n;i++)ans*=2;
k=n-m+1;
if(k<=0)printf("%lld",ans);
else
{
for(i=k;i>=1;i--)ans-=i;
printf("%lld",ans);
}*/
return ;
}
上一篇:arcgis api 4.x for js 结合 react 入门开发系列初探篇(附源码下载)


下一篇:wordpress设置“固定链接”后,页面404错误的解决方法