首页 > 代码库 > UVa 10943 - How do you add?
UVa 10943 - How do you add?
题目:求一个数字n拆成k个数字的拆法数,可以重复,可以有0。
分析:dp,组合数学。
方法1:dp
状态:f(i,j)为 j 拆成 i 个数字的方法数,则有f(i,j)= sum(f(i,k)) { 0 ≤ k ≤ j };
方法2:计数原理
隔板法:C(n+k-1,k-1)= (n+1)(n+2)... (n+k-1),
计算利用 C(n,m)= C(n-1,m-1)+ C(n-1,m)即可。
说明:╮(╯▽╰)╭。
方法一:dp
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int F[101][101]; int main() { for ( int i = 0 ; i < 101 ; ++ i ) for ( int j = 0 ; j < 101 ; ++ j ) F[i][j] = 0; for ( int i = 0 ; i < 101 ; ++ i ) F[1][i] = 1; for ( int i = 1 ; i < 101 ; ++ i ) for ( int j = 0 ; j < 101 ; ++ j ) for ( int k = 0 ; k <= j ; ++ k ) F[i][j] = (F[i][j]+F[i-1][j-k])%1000000; int n,m; while ( scanf("%d%d",&n,&m) && n+m ) printf("%d\n",F[m][n]); return 0; }方法二:计数原理
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int C[201][201]; int main() { for ( int i = 0 ; i < 201 ; ++ i ) for ( int j = 0 ; j < 201 ; ++ j ) C[i][j] = 0; for ( int i = 0 ; i < 201 ; ++ i ) C[i][0] = 1; for ( int i = 1 ; i < 201 ; ++ i ) for ( int j = 1 ; j <= i ; ++ j ) C[i][j] = (C[i-1][j]+C[i-1][j-1])%1000000; int n,m; while ( scanf("%d%d",&n,&m) && n+m ) printf("%d\n",C[n+m-1][m-1]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。