第七十二天 P1025 [NOIP2001 提高组] 数的划分
admin
2024-03-20 14:34:40

题目描述

将整数 nn 分成 kk 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：n=7n=7，k=3k=3，下面三种分法被认为是相同的。

1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.

问有多少种不同的分法。

输入格式

n,kn,k （6

输出格式

11 个整数，即

dp能解这道题是我没想到的。

思路：这题看成小朋友分糖问题。把i看成糖的总数，j看成小朋友个数

先把每一个小朋友都分为1个糖，剩下糖的数量为i-j。可以把剩下的糖分给1，2 ，3...j个小朋友，总分法就是dp[i][j]=dp[i-j][1]+dp[i-j][2]+...dp[i-j][j],可以写出下一个公式为dp[i-1][j-1]=dp[i-j][1]+dp[i-j][2]+...dp[i-j][j-1]

最后令1式-2式就可得到递推公式为dp[i][j]=dp[i-1][j-1]+dp[i-j][j];

#include
#includeusing namespace std;int dp[210][7];int main()
{int k,n;cin>>n>>k;for(int i=1;i<=n;i++){dp[i][1]=1;dp[i][0]=1;}for(int i=2;i<=n;i++){for(int j=2;j<=k;j++){if(i>=j)dp[i][j]=dp[i-1][j-1]+dp[i-j][j];	}} cout<

明天还有2500字政治论文没交，头疼 

 

上一篇：AcWing第80场周赛总结

下一篇：【数字IC基础】状态机FSM（ Finite State Machine）

相关内容

热门资讯

山水皆有情！丽江两山一江的千年... 去过丽江、走过虎跳峡的人，大概率都听过哈巴雪山和金沙江的传说。很多人站在峡谷之下，望着奔腾不息的金沙...
活力中国调研行丨“殷”你而来 ... 9月12日，游客在殷墟博物馆“甲骨文展厅”内参观。位于河南省安阳市的殷墟博物馆新馆是首个全景式展现商...
浦江之夜赴美好相逢，第37届上... 9月12日晚，黄浦江畔灯火璀璨，第37届上海旅游节大巡游在外滩中山东一路上演。不少观众早早便来到外滩...
美丽中国丨秋韵紫鹊界 梯田入画... 这是9月11日拍摄的紫鹊界梯田（无人机照片）。 金秋九月，湖南省娄底市新化县紫鹊界梯田稻谷渐次成熟。...
中国之巅奏响《共同的节日》，千... 千吨阻尼器，“迎世赛、游上海旅游节”。9月13日，由上海市文化和旅游局指导推出上海旅游·会客│巅峰之...