标签: 动态规划

20 篇文章

密码保护:ZROI – 19普转提 – Day5 – T3 – 背包
有 $n$ 个物品,编号为 $1$ ~ $n$,每个物品有重量 $w_i$,价值 $v_i$.
有 $m$ 个背包,编号为 $1$ ~ $m$,每个背包有容量上限 $t_i$.
物品 $i$ 能够放入背包 $j$,当且仅当 $t_j \geq w_i$.
现在选出 $n$ 个物品,使它们能够通过交换顺序满足:物品的重量和价值从左到右均单调不降。且这 $n$ 个物品能分别放入不同的背包中。
求 $\rm{Max\_n}$.
洛谷 – P5664 – [CSP-S2019]Emiya家今天的饭
一共 $n$ 种烹饪方法和 $m$ 种主要食材,每道菜对应一种方法和一种食材。使用第 $i$ 种方法和 第 $j$ 种食材,可以做出 $a_{i, j}$ 道不同的菜。求有多少个集合满足如下条件:
  • 非空
  • 每道菜烹饪方法互不相同
  • 集合中每种主要食材的菜数不超过集合大小的一半
密码保护:ZROI – 19普及组 – Day2 – T4 – 与非门树
给定一棵 $n$ 个节点的有根树,每个点有点权。对于所有叶子节点,点权为 $0$ 或 $1$。非叶子节点分为两类,对于第一类,点权为其所有儿子节点的点权与非和;对于第二类,点权恒为 $h_i\in[0, 1]$,题目给定 $h_i$.
现在给叶子节点赋值。
存在 $A$ 种不同的赋值方法使得:若将所有第二类点变为第一类点,根节点的点权不变,一共存在 $B$ 种不同的赋值方法。
求 $\frac{A}{B}\bmod 998244353$.