首页 > 挑选方案问题
开通博客写题解
头像 雨__Ame__
发表于 2020-12-22 21:14:18
机房同学让我看的题，然后随便推了一下就出来了，本质上是生成函数裸题 考虑五种限制 update:机房同学说有地方手残写错了见谅qaq，已更正 1：可以取无限个，对应的生成函数为 2：有一个，对应的生成函数为 3：有四个，对应的生成函数为 4：无限但只能取偶数个，对应的生成函数为 5：无限但只能取的倍 展开全文
去ta的博客 赞 (20) 回复(9) 收起
头像 自由的走狗
发表于 2020-12-23 11:01:08
多写出几组数据，即可分析出规律: 0 1 1 3 2 6 3 10 4 15 5 21 dp[1] = dp[1- 1] + (1 + 1)dp[2] = dp[2 - 1] + (2 + 1)dp[3] = dp[3 - 1] + (3 + 1);可以利用dp解决，状态转移式为： dp[n] = 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 不是江小白
发表于 2021-09-04 21:09:47
1. 解法一：生成函数 1.1 思路 （由于公式有点多，但是耐心看下去你会发现没你想象中那么难懂这些公式，谢谢！）看到好些大佬都提到此题可以用生成函数解，那么我们先了解一些关于生成函数（Generating function）的基础知识。首先看定义： 专业地术语解释：在数学中，某个序列 的母函数（ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 简单666
发表于 2021-08-22 16:38:12
题意 有5个盘子，每个盘子有有限个或者无限个体积为 的面包，你有一个体积为 的背包，问刚好装满背包的方案数（两个方案不同当且仅当从某一个盘子中拿出的面包体积不同）。 方法一（暴力解法，不可AC）：分组背包 显然这是一个分组背包问题，其中第1个盘子对应着物体体积为1的完全背包问题，第2个盘子对应着物体 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 开车的阿Q
发表于 2021-08-20 22:45:28
描述 这是一篇面对初级coder的题解。 知识点：生成函数（母函数） 动态规划（背包问题） 难度：四星 题解 自助餐厅里有5个盘子，里面装的都是面包。 第1个盘子里有无限个面包； 第2个盘子里只有1个面包； 第3个盘子里只有4个面包； 第4个盘子里也有无限 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”