博客

洛谷1470 最长前缀 Longest Prefix
本题地址： http://www.luogu.org/problem/show?pid=1470

题目描述
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。
如果一个集合 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

看完题目我就蒙蔽了QAQ。。语文不好没治了；

后来看了半天才明白意思：给定一个字符串，把她的前缀分成一组字符集合中的几项（可以重复也可以不用一些），可行的最长前缀。

观察到“最长”估计是动态规划；应该是背包DP吧。。。

于是设计状态：

f[i] : 前i的字符的最长可行方案

方程：


f[i] = max(f[i-len[j]]+len[j]) j 是 字符串集合中的某项编号，len[j] 为该项的长度


f[i-len[j]] 就是 已知 i-len[j] – i 可以拆成一项，则只需调用f[i-len[j]] 就能知道之前的最大长度，再加上len[j]就是拆出 j 项后前i个字符的最大长度

要求 ：

f[i-len[j]] 不为0 即 之前的字符前缀合法

如果i-len[j] 是 0 ，则说明只拆成了一项，此时不用考虑上一条

可以把 i-len[j] 到 i 拆成 第 j 项

i足够长，长于第 j 项

目标：

max(f[i])


蒟蒻的思路好像很乱啊ＱＡＱ　给大家看下代码，求改进。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
const int maxn = 200010;
using namespace std;
char a[maxn];
int f[maxn];
char x[210][210];
int l[210];
int len;
int ans;
int check(int id,int idx)
{
    for(int i=0;i<l[id];i++)
       if(a[idx+i]!=x[id][i])
          return 0;
    return 1;
}
int main()
{
    int tot=0;
    while(scanf("%s",x[++tot])&&x[tot][0]!='.') l[tot]=strlen(x[tot]);
    char c[100]={0};
    while(~scanf("%s",c))
    {
        int ll=strlen(c);
        for(int i=0;i<ll;i++)
           a[++len]=c[i];
    }
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=tot;j++)
            if((i>=l[j]&&check(j,i-l[j]+1))&&(f[i-l[j]]!=0||i-l[j]==0))
                 f[i]=max(f[i],f[i-l[j]]+(l[j]));
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}