Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
对状态的理解f[i][j]表示前i种钱币,组成面值j,使用第i种钱币最少的数量 明明只是求j的可达性,却通过这么一个巧妙的状态, 使得复杂度减至O(N*V),N是组数 带二进制优化的分组背包是O(sum(log(num[i]))*V) 对于这状态的另一种理解 普通背包 j = 0时 遍历 v[i], 2 * v[i], 3 * v[i],..., n[i] * v[i] j = 1时 遍历 1 + v[i], 2 + 2 * v[i]... j = v[i]时 遍历 2 * v[i], 3 * v[i]... 发现和上面重了,这块重复的搜索很浪费啊,怎么解决呢 看到,如果n[i]有无穷大,那么j>=v[i]的会完全与j=0...v[i]-1的重复 但n[i]是有限的,只循环j=0...v[i]-1,有些数量不够, 需要借助之前物品的,就遍历不到了 一种想法是,尽量节省地使用物品i,记录i在凑成j时最少使用的数量 如果之前物品能够凑出j,那就不用使用物品i了 这样节省地遍历下j=0...v[i]-1,算起来时间复杂度还是O(N*V) 代码前面帖子里都有 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator