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 ybdesire at 2012-03-09 10:53:31 on Problem 1014
1、是不是背包?
    传统背包求的是最大价值,这里只需相等。所以,在背包的基础上,另c[i] = w[i](即每件物品的重量与价值相等),就转化成背包了。最终即判断f[v]是不是等于v(背包能承受的重量)
2、二进制拆分后数据数组多大?
    极端假设每个数的最大个数为20000。则 2^0+2^1+...+2^n = 20000, 可得n=15,所以split[N]中N=6*15=90;我的设置为90就过了不用像其他人说的设为几兆
3、血的教训
    C开辟的数据和malloc的空间,一定要先memset为0,否则无辜WA....

看不懂的,看背包九讲去...


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