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

终于过了,果然是 对 tie 的判断出了问题

Posted by WhoKnows at 2006-04-21 13:29:33 on Problem 1010
In Reply To:求助: 我很菜, 这个题目, 我想用 动态规划做, 这样做在取最优解的几次比较时很麻烦, 但是我想算法上也许是行得通的 Posted by:WhoKnows at 2006-04-21 11:59:52
> 我定义的状态是: 
> opt[1..n][0..4][0..max*4]
> 
> 1..n 表示输入的 stamp 的类型数
> 0..4 表示用了几张 stamp
> 0..max*4 max 是指输入 stamp 面值的最大值, 最多只能用 4 张, 所以乘 4 倍
> 
> 状态 opt[i][j][k] 的意义是: 
>     取用了前 i 种类型的 stamp, 用了 j 张, 总面值是 k 时, 所用 stamp 类型
>     数的最大值, 当然还保存了很多 辅助进行比较的参数, 比如说 stamp 最大面
>     值 等等.
> 
> 状态转移方程和普通的动态规划没什么区别
> 
> 难点在于: tie 的判断, 我的 tie 可能有问题, 但是看不出来的.
> 
> 请问大家, 我的思路可行么? 一直 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