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

我想了一个n^2的DP，一直都是WA，是算法不对吗？（见内）

Posted by mostleg at 2005-07-29 18:20:42
In Reply To:O(n^2),自己想吧,应该不难想到的 Posted by:xfxyjwf at 2005-07-29 18:08:03

令best[i][j]表示左边从1到i，右边从1到j的最优解。
状态转移就是从best[i][j-1]，best[i-1][j]或者是best[a-1][b-1]+2中取最大的（a,b表示从i,j向上能画的最低的交叉线）

Followed by:

没错 (117) xfxyjwf 2005-07-29 18:21:58
ft~~~~~~~我也用这个算法，但是被我写成了N^4的，我真猪头 (117) sunmoonstar_love 2005-07-29 18:23:02
- 是不是要有个预处理的表？ (0) sunmoonstar_love 2005-07-29 18:30:28
  - 是...可我为什么WA啊，我还重敲了一次 (0) mostleg 2005-07-30 12:10:33
    - 我贴一下吧，求大牛们帮忙看看： (1051) mostleg 2005-07-30 12:16:27
      - Re:我贴一下吧，求大牛们帮忙看看： (1264) xfxyjwf 2005-07-30 12:19:55
        多谢！可是改了之后还是WA。。。还有什么错误呢？ (1134) mostleg 2005-07-30 13:06:26
      - Re:我贴一下吧，求大牛们帮忙看看： (1195) frkstyc 2005-07-30 13:08:52
        好程序，空re一个 (0) frkstyc 2005-07-30 13:10:08
      - Re:我贴一下吧，求大牛们帮忙看看： (1452) frkstyc 2005-07-30 13:09:47
        不是这样改吧？ (0) mostleg 2005-07-30 13:12:58
        我的和你的别的都一样就这不同，然后我的能AC，除非你rpwt (0) frkstyc 2005-07-30 13:14:02
        我的upl[x][y]表示左侧的x连到右侧y“之上”最低的位置。确实应该是+1吧？或者你的意思是我越界了？ (0) mostleg 2005-07-30 13:18:01
        显然你这样写的话和下面写[a-1][b-1]就是矛盾的 (0) frkstyc 2005-07-30 13:23:22
        Re:显然你这样写的话和下面写[a-1][b-1]就是矛盾的 (137) mostleg 2005-07-30 13:27:43
        请重新思考 (157) frkstyc 2005-07-30 13:31:01
        糊涂了。。。我试着这样改，还是WA。。。 (0) mostleg 2005-07-30 13:35:19
        那么更加要重新思考 (29) frkstyc 2005-07-30 13:36:44
        狂晕,我rpwt这么大么？变量名都和别人重了？真的是自己写的呀！！！ (31) mostleg 2005-07-30 13:39:05
        跳进黄河也洗不清了。。。 (0) mostleg 2005-07-30 13:40:36
        rpwt (0) frkstyc 2005-07-30 13:50:02
        找到错之后你会跳的 (0) frkstyc 2005-07-30 13:55:57
      - 程序错倒是没错，不过你的确有严重的rpwt (1195) frkstyc 2005-07-30 13:52:29
        打错变量…… (0) frkstyc 2005-07-30 13:53:28
        这个错误真难看出来 (10) xfxyjwf 2005-07-30 13:54:51
        你也看见了吧，就是那里 (14) frkstyc 2005-07-30 13:55:23
        十分感谢两位。我真该准备跳了。。。 (0) mostleg 2005-07-30 13:58:05
        “真”字不要，“该”字也不要 (0) frkstyc 2005-07-30 13:58:49
        我也发现了。要不是您说我抄袭，我就不会想到去搜一下cross match.结果发现了PKU1692，然后。。。 (49) mostleg 2005-07-30 13:56:06

Post your reply here:

Home Page Go Back To top