题目描述 Description
一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数。
输入描述 Input Description
输入文件只一行，两个正整数N，M( 1<N<50，2≤M≤5)
输出描述 Output Description
输出文件只有一个正整数S，表示方案总数。
样例输入 Sample Input
4 3
样例输出 Sample Output
13
数据范围及提示 Data Size & Hint
( 1<N<50，2≤M≤5)
f[n][i]表示这n个坑，有i个连续放着物品。
明显地存在 f[n][0]=Σf[i][0], f[n][i]=f[n-1][i-1]。
1 #include <cstdio> 2 3 inline void read(int &x) 4 { 5 x=0; register char ch=getchar(); 6 for(; ch>'9'||ch<'0'; ) ch=getchar(); 7 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 8 } 9 10 #define LL long long 11 int n,m; 12 LL sum[55][9],ans; 13 14 LL DFS(int now,int cnt) 15 { 16 if(now<cnt) return 0; 17 if(sum[now][cnt]) return sum[now][cnt]; 18 if(!cnt) 19 for(int i=0; i<m; ++i) 20 sum[now][cnt]+=DFS(now-1,i); 21 else sum[now][cnt]=DFS(now-1,cnt-1); 22 return sum[now][cnt]; 23 } 24 25 int AC() 26 { 27 read(n),read(m); 28 sum[0][0]=sum[1][0]=1; 29 for(int i=0; i<m; ++i) 30 ans+=DFS(n,i); 31 printf("%lld ",ans); 32 return 0; 33 } 34 35 int Aptal=AC(); 36 int main(){;}
1 #include <cstdio> 2 3 inline void read(int &x) 4 { 5 x=0; register char ch=getchar(); 6 for(; ch>'9'||ch<'0'; ) ch=getchar(); 7 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 8 } 9 10 #define LL long long 11 int n,m; 12 LL f[55][9],ans; 13 14 int AC() 15 { 16 read(n),read(m); 17 f[0][0]=f[1][0]=f[1][1]=1; 18 for(int i=2; i<=n; ++i) 19 { 20 for(int j=0; j<=i&&j<m; ++j) 21 if(!j) f[i][j]+=f[i-1][j]; 22 else 23 { 24 f[i][0]+=f[i-1][j]; 25 f[i][j]=f[i-1][j-1]; 26 } 27 } 28 for(int i=0; i<m; ++i) ans+=f[n][i]; 29 printf("%lld ",ans); 30 return 0; 31 } 32 33 int Aptal=AC(); 34 int main(){;}