Detail of message

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

dp

Posted by frkstyc at 2005-07-25 01:10:04 on Problem 1923
In Reply To:这道题有公式吧？很多0ms 32k 的，在纸上乱画，找到些规律（把n条线分成i组平行线得到交点数），但是肯定是做不到 0ms 的，高人指点一下！ sothink怎么做的？ Posted by:sunmoonstar_love at 2005-07-25 01:03:40

Followed by:

感觉像一种递推，纵向是差为递增数列的数列，第一项是n*(n-1)/2, 横向是差为1 的等差数列，递推结束条件是找到m跳出，或是未找到，约束条件是构成几组平行线的直线数小于n (120) sunmoonstar_love 2005-07-25 01:29:10
- 似乎可以做成广搜 (128) sunmoonstar_love 2005-07-25 01:30:38
  - dp，写成记忆化搜索 (0) frkstyc 2005-07-25 01:33:07
    - 呵呵，不怕你笑，我没接触过记忆化搜索，没看过呢^_^,按我的想法，时间复杂度o(n),实际上也许不到n/2，空间是o(1), 记忆化搜索，不知是不是和这个差不多 (0) sunmoonstar_love 2005-07-25 01:52:50
      - ................................. (0) frkstyc 2005-07-25 02:19:21
        cong~~~~~~~~~~终于用DP把他搞掉了 (0) sunmoonstar_love 2005-09-04 23:35:51
        再cong一个，虽然用了78ms (0) sunmoonstar_love 2005-09-04 23:38:00

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator