题目描述
在一次运会上，有一个比赛项目，共有N个人参加比赛，要将这N个人分组，每组人数不少于K个，问有多少种分组方式？
比如有16个运动员，每组人数不少于5个，共有6种分组方式：
(1) 分一组，为16人；
(2) 分二组，分别为11人、5人；
(3) 分二组，分别为10人、6人；
(4) 分二组，分别为9人、7人；
(5) 分二组，分别为8人、8人；
(6) 分三组，分别为6人、5人、5人。
注意：6+5+5，5+6+5，5+5+6为同一种，只算一种分组方式；
输入
输入共一行为两个整数N, K。表示有N个运动员分组，每组不少于K个人(1 ≤ K ≤ N ≤ 500)。
输出
输出共一行为一个整数，表示分组数。
样例输入 Copy
16 5
样例输出 Copy
6
这是一道比较经典的 组合数学 题，像极了高中时代求n球放在m个盒子里的方案数量
题意转化：
n个人分组，每组至少k人，那么说我们一定能够得到最多能分 t = n / k 组， 下取整
然后将n个人分组，每组至少k人的方案数 就等于 n人分1组 + 分2组 + … + 分 t 组的方案数量
将n人分 i 组(1 <= i <= t) 的方案数量：{
每组先安排k个人，然后会剩下rest = n - k * i 人
然后问题就转化为将剩下的rest人分到i组里面，允许有空的方案数啦(是不是很熟悉)
}
记得开 __int128，否则会wa
Code:
__int128 n,k,t; __int128 dp[507][507]; void getdp(){ for(int i=0;i<=n;i++){ for(int j=0;j<=t;j++){ if(i == 0 || i == 1 || j == 1) dp[i][j] = 1; } } for(int i=2;i<=n;i++){ for(int j=1;j<=t;j++){ if(i < j) dp[i][j] = dp[i][j-1]; else dp[i][j] = dp[i][j-1] + dp[i-j][j]; } } } int main() { n = Read(),k = Read(); t = n / k;///最多t组 __int128 ans = 0; getdp(); for(__int128 i=1;i<=t;i++){ __int128 rest = n - k * i; if(rest == 0) { ans ++; continue; } ans += dp[rest][i]; // write(ans); // puts(""); } write(ans); return 0; }
当然，也可以记忆化搜索一手:
Code:
__int128 vis[507][507]; __int128 get(__int128 n,__int128 m){ if(vis[n][m]) return vis[n][m]; if(n == 1 || m == 1 || n == 0) return vis[n][m] = 1LL; if(n < m) return vis[n][m] = get(n,m-1); if(n >= m && m > 1) return vis[n][m] = get(n,m-1) + get(n-m,m); } int main() { __int128 n = Read(),k = Read(); __int128 t = n / k; __int128 ans = 0; for(__int128 i=1;i<=t;i++){ __int128 rest = n - k * i; if(rest == 0) { ans ++; continue; } ans += get(rest,i); } write(ans); return 0; }
