当前位置：首页 > 编程日记 > 正文

多重集表示合json数据_计数DP（划分数，多重集组合数）

编程日记 2024-04-27 15:00:00

划分数：把n个无区别的物品划分成不超过m组。 dp[i][j]=j的i划分的总数。 dp[i[j]=dp[i][j-i]+dp[i-1][j] 即：将j个物品分成i份，有两种情况：每份划分都大于等于1 dp[i][j-i]; 存在有一份以上用0划分dp[i-1][j]

int main()

{

int n,m;

cin>>n>>m;

dp[0][0]=1;

for(int i=1;i<=n;i++)

for(int j=0;j<=n;j++)

{

if(j>=i)

dp[i][j]=dp[i][j-i]+dp[i-1][j];

else

dp[i][j]=dp[i-1][j];

}

cout<

return 0;

}

多重集组合数：n种物品，第i种有a[i]个，从中选取m个，有多少种不同的选择方法？ dp[i+1][j]:从[0, i]号物品中选取j个物品的方法。 dp[i+1][j] = dp[i][j] + dp[i+1][j-1] 这是我们很直观想到的一个递推关系：dp[i][j]表示从i号物品中选0个， dp[i+1][j-1]从i号物品中至少选择1个实际上，由于是多重集而不是完全集合，我们已经选取了一个i号物品，所以dp[i+1][j-1]表示的不是从i号物品中选择至少一个的数目，因为dp[i+1][j-1]包含了选取a[i]个i号物品(此时总共选择了a[i]+1个物品了)，这种情况是应该去掉。需要减去dp[i][j-a[i]-1],所以应该是###dp[i+1][j] = dp[i][j] + dp[i+1][j-1] - dp[i][j-1-a[i]];

void solve()

{

for(int i=0;i<=n;i++)

dp[i][0]=1;

for(int i=0;i

for(int j=1;j<=m;j++)

{

if(j-1>=a[i])

dp[i+1][j]=(dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]+mod)%mod;

else

dp[i+1][j]=(dp[i+1][j-1]+dp[i][j])%mod;

}

cout<

}

https://www.dkcj.cn/info/5304.html

多重集表示合json数据_计数DP（划分数，多重集组合数）

相关文章：

搭建PHP环境遇到的问题!!

linux进程间通信：shell管道 | 的实现

Golang的接口

mysql 5.6.15_mysql-5.6.15-win32.zip免安装配置

jquery treeview 树形插件

spark调优（一）-开发调优，数据倾斜，shuffle调优

linux进程间通信：popen函数通过管道与shell通信

新的小游戏发布啦。Pop Jungle

mysql thread safe_Windows环境下完全手工配置Apache、MySQL和PHP（Thread Safe）

点滴积累【C#】---检验编号在本表中自动生成，与其他表无关

Alpha冲刺（9/10）

linux进程通信：pipe实现进程同步

（转）MySQL联表查询

极小连通子图和极大连通子图_强连通分量与拓扑排序

INTERVAL数据类型-007学习笔记

scrapy模拟用户登录

linux 系统调用 open函数使用

配置zendframework开始工作（加入环境变量）

mysql计算两gps坐标的距离_mysql 计算两坐标间的距离

（转）mxArray数据类型

Bootstrap笔记（记录不会的知识）

linux 系统调用 read,write和lseek 使用

简单有趣的matlab小程序_超实用有趣的五个小程序推荐

一些linux下的性能监测工具

uva 10183 How many Fibs?

2018/11/29 一个64位操作系统的设计与实现 02 (安装nasm)

a-awk 计算数值最大，最小，平均值并保留指定位数

第18章：MYSQL分区

mysql属性配置提高查询_MYSQL性能优化-安装时优化参数配置提高服务性能

c++引用的自我见解