A41016. 化学品问题
填空题
中等
知识点
题目描述
化学品问题
题目描述
一个实验室有N个放化学品的试管，排列在一条直线上。如果连续M个试管中放入药品，则会发生爆炸，于是，在某些试管中可能不放药品。
任务：对于给定的N和M，求不发生爆炸的放置药品的方案总数
输入格式
第一行是一个正整数L，代表输入数据的组数
接下来L行，每行有两个正整数N，M( 1＜N＜32，2≤M≤5)
输出格式
输出L行，每行只有一个正整数S，表示对应输入数据的方案总数。
样例输入
2
4 3
3 2
样例输出
13
5
参考答案
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int f(int n, int m, int t[33][6])
{
if(t[n][m])
return t[n][m];
if(n<m)
{
t[n][m]=pow(2,n); //n<m，随便放吧2的n次方
return t[n][m];
}
if(n==m) //当n=m的时候
{
t[n][m]=pow(2,n)-1; //有2的n次方减一种方法，只要不是全部都是药品就行
return t[n][m];
}
t[n][m]=f(n-1,m,t)+f(n-1,m,t)-f(n-1-m,m,t);
return t[n][m];
}
int main()
{
int t,n,m;
scanf("%d", &t);
while(t--)
{
int t[33][6]= {0};
scanf("%d %d", &n, &m);
printf("%d\n", f(n, m, t));
}
return 0;
}
上一题
下一题