UVa 10943 How do you add?【递推】

题意：给出n,k，问恰好有k个不超过n的数的和为n的方案数有多少

可以隔板法来做现在有n个小球放到k个盒子里面，盒子可以为空

那么就是n-k+1个缝隙，放上k-1个隔板（k-1个隔板就分成了k份）所以总的方案数为 C(n+k-1,k-1)

所以可以转化为C(i,j)=C(i-1,j)+C(i,j-1)

即为d[i][j]=d[i-1][j]+d[i][j-1],

d[i][j]表示j个数的和恰为i的方案数

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[][];

 int main(){

     int k,n;

     memset(d,,sizeof(d));

     for(int i=;i<=;i++) d[][i]=;

     for(int i=;i<=;i++){

         for(int j=;j<=;j++){

             d[i][j]=(d[i-][j]+d[i][j-])%mod;

         }

     }

     while(scanf("%d %d",&n,&k)!=EOF&&n&&k){

         printf("%d\n",d[n][k]);

     }

     return ;

 }

巴特西

UVa 10943 How do you add?【递推】

最新文章

热门文章