鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 操作系统维护 > 其它 > >

洛谷 P1470 [USACO2.3]最长前缀 Longest Prefix

来源:互联网 作者:佚名 时间:2017-09-06 09:22
题目描述 在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列(即元素)很感兴趣。 如果一个集合 P 中的元素可以通过串联(元素可以重复使用,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那

题目描述

在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列(即元素)很感兴趣。

如果一个集合 P 中的元素可以通过串联(元素可以重复使用,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素。元素不一定要全部出现(如下例中BBC就没有出现)。举个例子,序列 ABABACABAAB 可以分解为下面集合中的元素:

{A, AB, BA, CA, BBC}

序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序,输入一个元素集合以及一个大写字母序列 S ,设S'是序列S的最长前缀,使其可以分解为给出的集合P中的元素,求S'的长度K。

输入输出格式

输入格式:

 

输入数据的开头包括 1..200 个元素(长度为 1..10 )组成的集合,用连续的以空格分开的字符串表示。字母全部是大写,数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ,长度为 1..200,000 ,用一行或者多行的字符串来表示,每行不超过 76 个字符。换行符并不是序列 S 的一部分。

 

输出格式:

 

只有一行,输出一个整数,表示 S 符合条件的前缀的最大长度。

 

输入输出样例

输入样例#1:
A AB BA CA BBC
.
ABABACABAABC
输出样例#1:
11

说明

翻译来自NOCOW

USACO 2.3

 

【分析】

map大法好,本来以为会慢,结果还可以。

然后就是dp的思想啦,能达到的点都标记为true,最后从后往前找最大的点。

 

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 map<string, bool> Map;
 5 string s, str;
 6 bool dp[200025];
 7 int len;
 8 
 9 void init() {
10     while (cin >> s && s!=".")
11         Map[s]=true;
12     str=" ";
13     while (cin >> s)
14         str+=s;
15     len=str.length()-1;
16     dp[0]=true;    
17 } 
18 
19 void DP() {
20     for (int i=1;i<=len;++i)
21         for (int j=1;j<=min(i, 10);++j) 
22             if (dp[i-j] && Map[str.substr(i-j+1, j)]) {
23                 dp[i]=true;
24                 break;
25             }
26     for (int i=len;i>=0;--i)
27         if (dp[i]) {
28             cout << i << endl;
29             return;    
30         }
31 }
32 
33 int main() {
34     init();
35     DP();
36 }

 

上一篇:Django_随机验证码
下一篇:次短路
网友评论
<