zcmimi's blog

arrow_back背包共7篇文章

avatar
zc
2020-02-27 22:12:00
查看原题

点击跳转

能凑出的钱: 使用多重背包(二进制优化)

找零: 使用完全背包

avatar
zc
2020-01-20 23:48:00
查看原题

点击跳转

按斜率建图

然后跑背包

avatar
zc
2020-01-19 21:11:00
查看原题

点击跳转

f[k][i][j]表示前k种面值,Ai元,Bj元最少交换几张

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先考虑每种硬币可以用无数次

f_i表示金额为i有多少种方案

f_i = \sum_{j=1}^4 f_{i-c[j](i \ge c_j)}

我们再来考虑硬币使用次数有限制怎么办

不合法的情况有:

1超额

1,2超额

1,3超额

1,4超额

1,2,3超额

1,2,4超额

1,3,4超额

1,2,3,4超额

...

要注意的是在多种硬币限制的情况下可能会减去多次,或加上多次

比如1超额,2超额,(1,2同时超额被减去两次,这是就要加回来

(1,2,3)(1,2,4)又是多算的...

是不是更直观的了解了容斥?

为了方便,我们可以枚举二进制下状态来更加优美实现。

(当有奇数种不合法的时候减去,偶数种不合法时加上)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Rainbow-Ride top: 0

用并查集合并联通块,然后背包

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

如果没有时间限制那就是一个裸的完全背包

我们可以先按时间从大到小排序,保证如果选了后面作业能选的话不会影响当前作业

接着背包求出每天的最小花费

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

保证这个数不会超过500000

那么就是背包了

买卖股票有3种方法:

  1. 买,第二天卖了

  2. 不买(相当于买了然后卖了)

  3. 买了,过几天再卖(相当于买了了,接下来卖了再买了)

d-1次背包即可

1/1
Search
search