NeoRuTayE's blog

POJ2063 - Investment

2019-02-22

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

ACMC C++DP 完全背包

HDU2191 - 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

2019-02-22

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活直接套用多重背包模板即可

ACMC C++DP 01背包

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,..

ACMC C++DP 01背包

洛谷P1855 榨取kkksc03

2019-02-19

P1855 榨取kkksc03 一道01背包模板题，但多了一个维度。

ACMC C++

快速读入模板

2019-02-18

代码如下👇

ACMC C++DP 01背包

HDU3466 - Proud Merchant

2019-02-18

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 <..

ACMC C++DP 01背包