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

题目描述

将整数 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字政治论文没交，头疼 

 

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

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

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

相关内容

热门资讯

原创 清... 白酒，作为中国传统的烈性酒之一，一直以来都是中国文化中不可或缺的一部分。 白酒的香型多种多样，其中...
守护“秋天的第一杯奶茶” 一场秋雨一场凉 秋天奶茶最温暖 你的朋友圈是不是也被“秋天的第一杯奶茶”刷屏了。为守护消费者“捧在手...
以“品鉴官”为载体，贵州贵酒再... 摘要：第二季贵州贵酒绵柔酱香全国行，内核玩法全面升级。 当白酒行业在深度调整的“寒潮”中摸索前行，一...
豆汁儿配焦圈：北京早餐的暗黑传... 在北京早餐江湖里，豆汁儿配焦圈堪称最具争议的“暗黑传奇”。这对组合看似简单，却让食客爱憎分明，成为检...
多款无糖桃酥大揭秘！五黑、苦荞...
呕心沥血！化疗后食谱这个菜谱价... 在媳妇做完手术后进入化疗初期，我参考了医院和其他康复病友的食谱，研究出了一份康复菜谱。我认为它在提高...
烘焙品牌加盟推荐，麦安研面包店... 近年来，随着消费升级和生活节奏加快，烘焙行业迎来了爆发式增长。据行业数据显示，2024年中国烘焙市场...
粤港澳名厨共烹白蕉海鲈，国鲈美... 南都讯 记者李洁琼 8月20日，珠海斗门将化身美食的灯塔。一场以“中国‘年鱼’国鲈食尚”为名的粤港澳...
原创 伏... “小暑大暑，上蒸下煮”，入伏后天气一天比一天闷热，走两步就满头汗，嗓子干得总想喝水。这时候最该吃的当...
张家界6天5夜游价格！算清楚了... 嗨，朋友们！我是小李，刚和闺蜜从张家界浪回来，玩了整整6天5夜，价格真心给力！出发前我做了好多功课，...
“夏雨荷”周六“搬家”！将常驻... 齐鲁晚报·齐鲁壹点 李梦瑶 王贝艺 “夏雨荷”要搬家了！8 月18 日，记者从济南文旅集团旅游开发有...
2025北部湾开海节在防城港市... 8月16日，2025北部湾开海节在防城港市开幕。本次活动以“千帆竞发防城港 开海畅游海边山”为主题，...
在桐庐3天感知富春江，它究竟藏... 在浙江桐庐的3天时间里，我几乎每时每刻都在感知富春江。 富春江，得名于新安江与兰溪江的交汇，亦指新安...
重庆旅游防疫必看！最新避坑攻略... 在重庆迷路3次后，我悟了！ 刚下飞机就被重庆的8D魔幻地形上了一课。导航显示“直线距离200米”，...
拍照巨美！河南又一景区火了，号... 最近郑州人的朋友圈被一个新晋网红地刷屏了。 蓝天上悠悠地飘着绵软的白云，小鹿慢慢走着，周围是碧绿的草...
峄山“蜘蛛侠”：您随丢的垃圾却... 峄山上的 “蜘蛛侠” 用坚守守护每一寸风景 这份文明邀约请查收 当你沉醉于峄山的奇峰怪石、古柏苍松...
金狐点评|十一黄金周金狐差评榜... 十一黄金周金狐差评榜出炉，有你踩过的坑么？__金狐点评| 人在囧途！十一黄金周金狐差评榜出炉，有你踩...
原创 孩... 这个事件确实触及了公共服务中规则执行与人性化处理的矛盾点。核心争议在于：景区工作人员严格执行身高标准...
广西北海至涠洲岛航线停航两天 中新网北海8月18日电(翟李强 莫卫华)受热带低压影响，广西北海至涠洲岛航线18日—19日停航两天，...
成都海底捞皇冠酒店即将开业，将... 微成都报道8月18日，微成都注意到，IHG（洲际酒店集团）官网显示，成都海底捞皇冠假日酒店（下称“海...