Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

对状态的理解

Posted by cmonkey at 2012-02-17 00:07:57 on Problem 1742
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator