自动搬运

查看原文

来自洛谷，原作者为

	hhjtutuhe 遥遥无期……

搬运于2025-08-24 21:25:27，当前版本为作者最后更新于2020-06-06 17:42:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道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