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

Re:大家帮忙看看我的程序，有没有办法改进时间复杂性，老是超时

Posted by ruanrongbin at 2005-04-07 17:02:26 on Problem 1159
In Reply To:大家帮忙看看我的程序，有没有办法改进时间复杂性，老是超时 Posted by:ruanrongbin at 2005-04-07 16:58:17

我是用递归实现的，不过每次弟归都要调用两个子程序，复杂性是2的n次方，
有没有办法改进？
小弟在此先谢谢了。

Followed by:

如果想要改进的话就用记忆话搜索，重叠子问题太严重了，不过这题空间限制太紧了，最好还是递推，用滚动数组 (64) TN 2005-04-08 10:35:44
- 放宽到多少合适？ (0) hawk 2005-04-08 10:36:41
  - 5000*5000,大概50000KB应该可以了吧？ (0) TN 2005-04-08 10:39:26
    - 我想还是不要加好，那么些人都过了，虽然我还没做 (0) frkstyc 2005-04-08 10:40:33
      - 这个要看卡内存有多大意义了，如果没意义就不必了 (61) hawk 2005-04-08 10:42:32
      - 但是我觉得在空间上限制使得别人要去用滚动数组并不好，这样仅仅只是麻烦了，没有起到锻炼的作用 (0) TN 2005-04-08 10:42:58
        不过我看了一下当时比赛环境，机器内存只有32M (0) hawk 2005-04-08 10:44:48
        看来组委会是故意的...... (0) TN 2005-04-08 10:47:56
        必然了，我98年买的机子都128M了 (0) cpp051200448264 2005-04-08 10:48:57
        这个太猛了 (0) hawk 2005-04-08 10:49:42
        98年11月，PII350，rmb2340，这个时候已经有PII450了，超rmb3000啊 (0) cpp051200448264 2005-04-08 10:52:14
        2000年的时候，北大机房的好像也就32或者64M内存吧 (0) hawk 2005-04-08 10:49:13
        可是理论上说IOI应该使用最好的机子啊，反正都是赞助 (0) TN 2005-04-08 10:50:39
        1month ago，我在计算机系机房用了一台P166+32M+VC5来做测验，幸好全是送分题 (0) cpp051200448264 2005-04-08 10:50:46
        其实这样好，在本机能运行的交上去一般都不会tle或mle,运行不了的交上去没准也ac^_^ (0) TN 2005-04-08 10:53:11
        最后一项：投机 (0) cpp051200448264 2005-04-08 10:55:26
- Re:如果想要改进的话就用记忆话搜索，重叠子问题太严重了，不过这题空间限制太紧了，最好还是递推，用滚动数组 (14) nobody_is_me 2006-05-21 14:07:34
  - 这个题那么多状态memoization还是要慢不少吧 (18) frkstyc 2006-05-21 14:10:11

Post your reply here:

Home Page Go Back To top