Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
路径的保存用 前向指针 的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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator