题解 P1470 【[USACO2.3]最长前缀 Longest Prefix】

· · 题解

这是一道DP的题目

分析

在样例中，S能够组成的P中的元素的最长前缀为11个字符，即为A+BA+BA+CA+BA+AB.用f[i]表示前i个字符是否可以分解为集合中的字符，如钩可以就为真，不可以就为假。则很容易看出：f[i]的充要（充分必要）条件是：存在一个比i小的j，满足f[i]=true且从第j+1到第i是p中的一个元素。

伪代码如下所示：

if(f[j]=true && s[j+1...i]为集合P中的一个字符串（j从i~1 到 1~10 枚举）
  f[i]=true
else f[i]=false;

参考代码如下所示：

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string P[201],S=" ";
bool f[200001]= {1};
bool Check(int p)
{
  for(int i=0;i<n;i++)
  {
    int t=P[i].size();
    if(p>=t && f[p-t] && P[i]==S.substr(p-t+1,t))
    {
      ans=p;
      return true;
    }
  }
  return false;
}
int main()
{
  for(string s;cin>>s,s!=".";P[n++]=s);
  for(srting s;cin>>s;S+=s);
  for(int i=1;i<=S.size();i++)
    f[i]=Check(i);
  printf("%d\n",ans);
  return 0;
}

上面的参考代码中可以优化的算法是判断某段字符串是否是集合中某元素时，如果逐一与集合中的元素比较，有可能超时。。。。。。

有能力的巨佬可以尝试使用二分法或者STL中的set容器优化代码。写那么多不容易，点个赞再走呗TWT