首页 > 代码库 > 【codevs】5833 放置核弹

【codevs】5833 放置核弹

 

 

第一次发 DP or 递推,如果有什么 理解错误 or 理解不透彻 or 有更优解法,嗯,请神犇指出(毕竟我 DP or 递推 很弱)...

题目:

网址:http://codevs.cn/problem/5833/

技术分享

技术分享

大意:n个坑里不能有连续的m个核弹,求方案数

 

嗯,其实也不难,看到题目第一个想到的就是dfs...

结果数据范围...

技术分享

...

好吧,dfs TLE...

嗯,记忆化...

嗯,我不会... 

那么,好吧,想一下DP or 递推...

 

思路:

把n个坑分成两部分

第一部分是0(没有放,因为没有放也算一种)~m-1,在这个范围内,由于不超过m,因此都可以弄一次放和不放(也就是这里面随便放都可以),那么就得到一个公式——f[b]=(f[b-1]+f[b-2]+...+f[0])*2

第二部分是m~n,在这个范围内,因为超过m,所以要考虑一下连续m个坑不能都放核弹的情况,于是b-m之前的不能算在一起了,也只能有放和不放其中一种情况,因此又有一个公式——f[b]=f[b-1]+f[b-2]+...+f[b-m]

这样算下去,f[n]就是答案了...

写的我自己都有点乱,可能理解有误...

 

嗯,就是这样...

代码:

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int main(){
 5     int f[10000]={0},b,n,m,b1,sum=1;
 6     cin>>n>>m;
 7     for(b=0;b<m;b++)f[b]=sum%1000000007,sum=(f[b]+sum)%1000000007;//从0(没有)~m-1 都能放或不放核弹的情况 f[b]=(f[b-1]+f[b-2]+...f[0])*2
 8     for(b=m;b<=n;b++)
 9        for(b1=1;b1<=m;b1++)
10            f[b]=(f[b]+f[b-b1])%1000000007;//从m开始 每m个连续的坑里,不一定能放核弹的情况 f[b]=f[b-1]+f[b-2]+...f[b-m]
11     cout<<f[n]<<endl;
12 }
放置核弹

 

嗯,又是一篇博客...

为什么总是写 DP or 递推?因为我到现在都分不清DP和递推...

 

【codevs】5833 放置核弹