Tyvj P3119 核电站问题 动态规划

题目：http://tyvj.cn/p/3119

P3119 核电站问题

时间: 1000ms / 空间: 65536KiB / Java类名: Main

描述

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

输入格式

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

输出格式

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

测试样例1

输入

输出

题解：

动态规划

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 ;

 }