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

如果想要改进的话就用记忆话搜索，重叠子问题太严重了，不过这题空间限制太紧了，最好还是递推，用滚动数组

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

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

Followed by:

放宽到多少合适？ (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