NeoRuTayE's blog

Home

About

Archives

🧸

ACMCC++DP完全背包

POJ2063 - Investment

Investment   其实就是做若干次的完全背包,每做一次都更新一下钱的总数。需要注意的是,因为钱的总数可能会很大,所以需要进行缩小,以免MLE。缩小方法是,因为每一种证券的价钱都是1000的倍数,故我们可以将它们的价钱都缩小为原来的1/1000(而利息不变)。

Read more
ACMCC++DP01背包

洛谷P1417 烹调方案

P1417 烹调方案   依然是01背包。这道题跟之前HDU的那道merchant很像,都是要先算一个不等式,再根据这个不等式进行排序,然后再进行01背包。具体而言,是要解下面这个不等式:  a1 - (t0 + c1) x b1 + a2 - (t0 + c1 + c2) x b2 > a2 - (t0 + c2) x b2 +a1 - (t0 + c1 + c2) x b1 ==>   b2 c1 < b1 c2 具体代码如下: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define mst(a,b) memset(a,b,..

Read more
ACMCC++DP01背包

HDU3466 - Proud Merchant

Proud Merchant   这道题最难搞的地方在于如何处理“小于qi时不能买”这一要求。苦思冥想许久,依然不知如何解决,于是只好去看题解......   这道题的做法是首先将“商人”按照q-p排序,然后再进行01背包。为什么是按照q-p排序呢?假设有两件物品A,B,他们对应的p,q分别是p1,q1和p2,q2。如果这两件东西都要买,那么,如果先买A,就至少需要p1 + q2的钱才能把两件东西都买到;如果先买B,就至少需要p2 + q1的钱才能把两件东西都买到。为了买到尽可能多的东西,获得尽可能大的价值,就应该按照代价小的方式来买。也就是说,假如先买A比先买B所需的代价更小,就有p1 + q2 < p2 + q1,即q1 - p1 < q2 - p2。 代码如下: #include <..

Read more
ACMCC++DP01背包

HDU1864 - 最大报销额

最大报销额   这道题有两个需要注意的地方:一是题目说的“每项”其实是“每类”,也就是A类,B类和C类,而不是每个物品......(这题目表述有问题啊!);二是在计算时要将所有的数据扩大100倍然后再转为int,计算出最后结果后再缩小为原来的倍率,否则无法用钱数来做背包(浮点数无法作为数组下标)。

Read more
ACMCC++DP01背包

HDU2546 - 饭卡

饭卡   一道01背包的题目,特殊之处在于要先拿出5元用来买最贵的东西,剩下的钱即为背包,然后就是普通的01背包了。

Read more
1789101112