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 Stareven at 2011-01-03 21:56:03 on Problem 3260 and last updated at 2011-01-03 22:05:12
这题思路倒是好想,对FJ付款做一次多重背包得到pf[],对shopkeeper找零做一次完全背包得到rf[],然后查找min{pf[i]+rf[i-T]}
关键在于shopkeeper的找钱范围的确定。如果不加以限制,其找钱范围能达到10000*100*120,也就是10^8。极其不理想。。。。但是实际上,我们可以发现,其实最大范围也只需要到Vmax*Vmax就绝对够用了。(其实是V的最大值乘以次大值,好像进一步可以到两数的最小公倍数,就足够,然后,考虑这样取要排序,而且如果n==1的话要特殊处理,比较恶。。就多开一点了。。)超过Vmax*Vmax的部分,必然是不超过Vmax*Vmax的一个rf[]加上几个coins得到的。详细证明还真不太好说。。。但是绝对能证明的。。。

另外~单调队列确实有意思。。太好用了。。

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