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 WhoKnows at 2006-04-21 11:59:52 on Problem 1010
In Reply To:不要误导别人，看一下自己使用的语言的帮助，也可以看1001的hint Posted by:hawk at 2006-04-06 19:33:21 
我定义的状态是: 
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