数字number

 

题目大意

给定n，k，s，从1到n中取出k个数，使其之和等于s

求可行的方案数（模1e9+7）

 

题解

一眼dp,于是我去写了dfs，带着少的可怜的剪枝，快乐的tle着...

 

设 f[ i ][ j ][ q ] 表示在前 i 个数中选 j 个使其和为 q 的方案数

 

则 f [ i ][ j ][ q ]=f[ i-1 ][ j ][ q ]+f[ i-1 ][ j-1 ][ q-i ](j>=1)

 

f [ i ][ j ][ q ]=f[ i-1 ][ j ][ q ](j=0)

 

f[ i-1 ][ j ][ q ]表示不选第 i 个，f[ i-1 ][ j-1 ][ q-i ]表示选第 i 个

初始化f[0][0][0] = 1

 

最终答案为 f[ n ][ k ][ s ]

 

#include
       
        #define ll long longusing namespace std;int n,h,s;int f[55][55][2005];const int mod = 1e9 + 7;int main(){    freopen("number.in","r",stdin);    freopen("number.out","w",stdout);    scanf("%d%d%d",&n,&h,&s);    f[0][0][0] = 1;    for(int i = 1;i <= n;i++)        for(int j = 0;j <= i;j++)            for(int k = 0;k <= s;k++)                if(j >= 1)                    f[i][j][k] = (f[i -1][j][k] + f[i - 1][j - 1][k - i]) % mod;                else                    f[i][j][k] = f[i - 1][j][k] % mod;    printf("%d",f[n][h][s]);    return 0;}