How do you add?(递推)

题意:求将n分为k个数相加的种数。

如:n=20,k=2,则可分为:

0+20=20

1+19=20

2+18=20

.......

20 +0=20

共21种方案。

解析:令f(n,m)表示将n分为m个数相加的种数,则 f(n,m)=  ∑ f(n-i,m-1)   (0 ≤ i ≤n)

代码如下:

 # include<iostream>
# include<cstdio>
# include<set>
# include<cstring>
# include<algorithm>
using namespace std;
const int mod=;
int a[][];///a[i][j]表示把i分为j个数的方法个数;
int main()
{
int i,j,l,n,k;
memset(a,,sizeof(a));
for(i=;i<=;++i)
a[i][]=a[][i]=;
for(i=;i<=;++i){
for(k=;k<=;++k){
for(l=;l<=i;++l){
a[i][k]+=a[i-l][k-];
a[i][k]%=mod;
}
}
}
while(scanf("%d%d",&n,&k),n+k)
{
printf("%d\n",a[n][k]);
}
return ;
}

这道题和 UVA-12304 Race 如出一辙

或是http://www.cnblogs.com/20143605--pcx/p/4677157.html

上一篇:[ASP.NET MVC]笔记(三) 成员资格、授权和安全性


下一篇:牛客练习赛23-A/B/C/D/F