题解

12 条题解

  • 1
    @ 2022-04-15 09:18:53

    • @ 2022-05-12 21:50:27

      嘿嘿

  • 1
    @ 2019-05-20 16:24:56

  • 1
    @ 2019-05-20 16:24:15

    我还没提交

  • 0
    @ 2007-11-10 19:08:15

    当心辅词不能作结尾

    其他没什么了。朴素判匹配也能0ms

  • 0
    @ 2007-10-31 19:39:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    用Trie辅助转移,进行DP……

  • 0
    @ 2007-08-27 13:27:12

    ...............

  • 0
    @ 2006-11-13 20:52:41

    检索树存单词...

    DP出解...

    记录前I个字符,最后一个单词为名词或动词时最少的句子数和单词数,状态转移就是前I个字符,最后J个为一个单词,取所有合法情况中的最小值......

  • 0
    @ 2006-11-08 17:22:46

    理解那个破范式

    一个名词短语是一个名词前加若干个(可以为0)辅词。

    一个动词短语是一个动词前加若干个(可以为0)辅词。

    而一个句子是以名词短语开头,名动短语交换,最后可以以名词或动词短语结尾。

    搜索文章中i开头的所有名动短语,用链表分开存储。

    设dp表示文章中i开头文章在匹配j短语(1-名词,2-动词)后的最优解(解的状态是二维的)。

    如果j=1,此时i处匹配名词短语k后,可以令起一个句子(接一个名词短语),也可以在本句接一个动词短语。

    如果j=2,此时i处匹配动词短语k后,只能在本句接一个名词短语。

    用类动态规划的方法可以求出dp的值,需要输出的结果就是dp[1,1]。

    因为很多的dp值根本不需要计算,所以用记忆化搜索来做。

    时间复杂度最坏情况下是O(mn),m是文章长度。实际效果瞬间出解。

  • -1
    @ 2009-11-10 11:12:13

    Flag   Accepted

    题号   P1299

    类型(?)   动态规划

    通过   50人

    提交   151次

    通过率   33%

    难度   3

    哈哈哈,第50人

  • -1
    @ 2009-05-16 18:57:19

    交了N次每次错的还不一样,有超时有WA,无语了。。。。最多只过了6个...trie还没朴素高不知道怎么回事....

  • -1
    @ 2008-10-19 17:10:40

    看懂题,仔细想,别想复杂了

    开了个大Hash判重,复杂度是O(文章长度*单词长度)

    1.41K的代码……AC

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • -2
    @ 2009-10-06 09:08:17

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    字母检索树 秒杀

  • 1

信息

ID
1299
难度
5
分类
字符串 | 动态规划 点击显示
标签
递交数
114
已通过
36
通过率
32%
被复制
3
上传者