首页 > ACM题库 > HDU-杭电 > hdu 2664 Harry Potter and His Magic Scroll待解决[解题报告]C++
2014
02-12

hdu 2664 Harry Potter and His Magic Scroll待解决[解题报告]C++

Harry Potter and His Magic Scroll

问题描述 :

Harry Potter want to make some scrolls to improve his magic power. He has a very big incantation dictionary, and the content of a scroll, must be a continuous passage from the dictionary. To make the scroll more powerful, Harry pick out a few powerful magic words, and want the scroll contains them. Given such magic words, where to start and where to end, to make the total number of words Harry Potter must write down for a scroll minimum? If there are some passages whose length are equal, choose the one which start first.

输入:

The first line is the number of cases.
For each case, there will be the content of the dictionary, which end with a line contains a single "#". Each line of the dictionary will not contain more than 2,000 characters, ant it will contain no more than 100,000 words. In a dictionary, Words are only splited by a single space. A word MAY in two lines.
Then followed by a line contain a integer T, indicates the number of scrolls. For each scroll, First line is an integer m meaning the number of magic words that the scroll must contain, then followed by m such magic words. The length of a word will not exceed 20.

输出:

The first line is the number of cases.
For each case, there will be the content of the dictionary, which end with a line contains a single "#". Each line of the dictionary will not contain more than 2,000 characters, ant it will contain no more than 100,000 words. In a dictionary, Words are only splited by a single space. A word MAY in two lines.
Then followed by a line contain a integer T, indicates the number of scrolls. For each scroll, First line is an integer m meaning the number of magic words that the scroll must contain, then followed by m such magic words. The length of a word will not exceed 20.

样例输入:

1 
Harr 
y Potter want to make some scrolls to improve his magic power. 
# 
2 
2 
Harry 
Potter 
1 
to 

样例输出:

0 11 
18 19 


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法