2025.11.26

P1164

dp_{i,j}

表示前

i

个物品恰好放满

j

的方案数。
答案：

dp_{n,m}

。
初始化：

dp_{0,0}=1

。
转移：

CPP

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        dp[i][j]=dp[i-1][j]/*不选 j*/+dp[i-1][j-w[i]]/*选 j*/;
    }
}

应老师要求，添加“为什么这样就能做到恰好花完钱”。

因为我们的

dp_{i,j}

在普通的 01 背包中那

j

的钱是可用可不用的。（dp[i][j]=dp[i-1][j]），但是这里是必须塞满的，因为：

这个菜 $i$ 不选，那么就是前 $i-1$ 个菜花 $j$ 块钱。
这个菜 $i$ 选，那么就是前 $i-1$ 个菜花 $j-w_i$ 块钱，然后第 $i$ 个菜花 $w_i$ 块钱。

画个图吧。

普通的 01 背包是这样的：

PLAIN

0 0 0 0 0 - - -
    > 0 为用了，- 为没用

然而这种“计数”的 01 背包是这样的：

PLAIN

0 0 1 1 1 2 2 4
    > 数字为用了第几个

P1926

如果要刷题多就要做作业少。

做作业：最少时间，

k

分以上，“答案”使用精卫填海的求法。
刷题：重量为刷题时间，价值为

1

，使用贪心或 dp。

ABC054D

状态：

dp_{i,j}

为 A 元素

i

克，B 元素

j

克的代价最小值。
答案：求满足

i÷j = M_a÷M_b

的

dp_{i,j}

的最小值。

所有物品 A 元素和为第一个背包容量。
所有物品 B 元素和为第二个背包容量。

P1734

背包容量为

S

，物品是数值

i

，重量是

i

，价值是

i

的因数和。

转化为 01 背包。

P2392

不同科目独立做，最后求和就行。
对于一门科目，所有题分配给左右脑的时间越接近越好。
两半脑的时间是有关系的，知道了一个半脑的，就知道了另一个半脑的。
所以可以以用时

\le sum÷2

的半脑为研究对象，

sum

为一科时间和。

转化为以

sum÷2

为容量，题目耗时为重量和价值的 01 背包问题。
跑 01 背包后，我们知道用时大的半脑才是答案，而用时小的半脑答案为

dp_{sum÷2}

，故单科答案为

sum-dp_{sum÷2}

。

单科过程重复四次。

来追梦笔记 RAM

文章操作