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 majia_ at 2009-11-14 13:04:10 on Problem 1837
In Reply To:此言并不差 Posted by:tzkq at 2009-11-14 09:57:22
> 其实感觉 像此题这种类型的并不属于dp范畴
> 
> 虽然程序看起来使用的是递推这一过程,但总不能说开个二重循环就是dp吧
> 
> 
> 
> 如果只从求解上来讲(不考虑数据值的范围), 只有枚举这唯一途径, 而此题的复杂度为O(20^20), 大约等于 10^26, 微机是很难在短时间内求解的。
> 
> 
> 而此题还有另一个限制, 就是数据值的范围, 虽然状态数那么多, 但是它们的范围有限
> 
> 这个时候, 状态产生大量重复, 于是, 程序可以优化为压缩这些重复状态, 从而减少开销
> 
> 
> 在实现的过程中, 确实划分了阶段, 但这个过程更像是枚举, 优化过后的枚举
> 
> 在朴素枚举当中, 阶段数与复杂度呈指数关系, 而在此题这种特殊情况下, 每个阶段数的最大不同状态数是有限的, 压缩以后就只是常数关系了
> 
> 
> 所以那 'dp'方程更像是一个'压缩状态'过程, 并没有求最优这一意思, 最后输出是状态数, 并不是最优解
> 
> 
> 再看一些常见的dp问题, 它们的意义很明确, 一定是求某种最优的结果, 其中普遍存在max,min
> 
> 最为关键的一点, 凡是能够被dp的问题, 都是p类问题, 它们的复杂度都为多项式表达式
> 
> 而该题类似的问题, 它们似乎往往都是npc问题, 它们很难有特别有效的算法
> 
> 像本题这种就是通过狭小的数据范围来进行优化, 但仍然逃不脱枚举这一本质, 
> 
> 如果稍微加大数据范围, 您看看还有更好的方法么?
> 
> 
> 
> 
> 
> 
> 当然,以上仅是自己的愚见  v_v
> 
> 
>  
> 

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