PKU 1742 Coins
楼教主男人八题的最简单一题,如果用传统的多重背包来解就是0(nmc)的复杂度,必然超时。
复习了一会儿背包九讲,研究出来了2种做法:
1.将c[i]分为二进制,例如15分为1 2 48个背包利用2^k个物品来背包,即可将c[i]优化到log(c[i])的程度。
2.还有一种称为是单调队列优化的方法,查阅了很多资料没有看到。
研究了解题报告后,大概方法是这样的,利用一个count[j]数组记录当前物品表达j这个状态时所需要的硬币数目,由于题目要求所枚举状态只需要知道是否可行,并不需要得到一个最优解,所以每次都只更新还没有更新过的状态,这样就不会出现某个状态用1个i硬币或2个i硬币都能表达的情况。