UVA 1401 Remember the Word(DP+字典树Trie) 题意:         给你一个由N个单词组成的词典,和一个字符串S。问你S由N中的单词组成的方法有多少种?字典中的单词可以重复使用但是不可重叠。 分析:         我们令d[i]=x表示S串的后缀[i,L-1]串有多少种构成方式(注意:如果令d[i]=x表示S串的前缀串[0,i]有多少种构成方式的话,就不能用字典树来查找单词了)。其中L=strlen(…

2014年4月7日 0条评论 2点热度 阅读全文

今天看了看背包九讲,自己写了下0-1背包和完全背包 王晓东《计算机算法分析与设计》上面给出的C++实现比较繁琐,相比而言这个版本更加简明 给出了测试数据 0-1背包问题C++实现 /*任务:计算0-1背包问题的最大价值 Sample Input 10 4 2 1 3 3 4 5 7 9 Sample Output 12 0 1 0 1 */ #include<stdio.h> #include<string.h> int c[20][1000];//c[k][y]为只允许装前k种物品,背包总…

2012年1月3日 0条评论 2点热度 阅读全文

     在输入的同时,进行一次DP,计算出从左到右的最大值,并把它保存在数组dp的对应的下标元素中,这样之后,对于下标为i的元素,它其中保存的便是前面所有元素可能的最大连续和。再从右到左进行一次DP,计算从右到左的最大连续和。假设此时已经算到下标为i的元素,那么将sum+dp[i-1]与ans进 行比较,将ans取较大者。最后当i到2的时候ans中的值即为所求的最大值。 #include <iostream> using namespace std; int dp[100…

2010年11月27日 0条评论 1点热度 阅读全文