题目大意:给定一棵K叉树,一个节点下的K个节点的分数为i,求包含大于等于D的边的总分数为N的方案总数,mod 1e9+7。
这是一道很好的树形DP题,首先看N和K两个条件,可以轻易的得到方程:
f[i][j]=(f[i][j]+f[i-k][j])%mod;
//f[i][j]表示总分为i,当前边分数到j的方案总数。
再看最后一个条件,我们仔细一想,不是只要将答案f[N][K]减去f[N][D-1]即可吗?
只需要减去小于D的所有方案不就好了吗?
answer=f[N][K]-f[N][D-1];
。。。。。。
所以这道题还是挺水的。
code:
#include <cstdio>
#define mod 1000000007
using namespace std;
int N,K,D;
int f[][];
int main(){
scanf("%d%d%d",&N,&K,&D);
for(int i=;i<=K;i++)f[][i]=;
for(int i=;i<=N;i++)
for(int j=;j<=K;j++)
for(int k=;k<=j;k++){
if(i-k>=)f[i][j]=(f[i][j]+f[i-k][j])%mod;
else break;
}
printf("%d",(f[N][K]-f[N][D-]+mod)%mod);
return ;
}