传送门
模拟赛T1就自闭了（
才不会说我是去刚T2了来着
感觉非常暴力的一个题？
出题人良心开大数据范围 n=100 还是原来的n^4*26算法我也是自闭了
不过貌似跑不到n^4？
真·大力出奇迹
一发记忆化搜索 就是f[l][r][c]表示 l~r化成一个字符c是否可行
然后大力出奇迹！= =+
枚举一下i，j表示第一个字符串的前i个和第二个字符串前j个合成的最短ancestor长度
再枚举从哪个开始合并
判一下就好啦
太真实了。谁敢写这种东西嘛= =+
【本来以为全场A的后来好像也只有4个人A？最后10min30爆搜一次写对还是很开心的= =+】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
using namespace std;
int n,l1,l2;
char s1[110],s2[110],fr[110][2],to[110][3];
int f1[110][110][27],f2[110][110][27];
int id(char ch){return ch-'a'+1;}
int dfs(char *ch,int f[][110][27],char goal,int l,int r)
{
if(r<l) return 0;
if(~f[l][r][id(goal)]) return f[l][r][id(goal)];
if(l==r) return ch[l]==goal;
memset(f[l][r],0,sizeof(f[l][r]));
for(int i=1;i<=n;i++)
for(int k=l;k<r;k++)
if(dfs(ch,f,to[i][0],l,k)&&dfs(ch,f,to[i][1],k+1,r))
{
f[l][r][id(fr[i][0])]=1;break;
}
return f[l][r][id(goal)];
}
int fin[110][110];
int main()
{
scanf("%s%s",s1+1,s2+1);
l1=strlen(s1+1);l2=strlen(s2+1);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
{
fr[i][0]=getchar();
while(fr[i][0]<'a'||fr[i][0]>'z') fr[i][0]=getchar();
to[i][0]=getchar();
while(to[i][0]<'a'||to[i][0]>'z') to[i][0]=getchar();
to[i][1]=getchar();
//printf("%s %s",fr[i],to[i]);
}
memset(f1,-1,sizeof(f1));
memset(f2,-1,sizeof(f2));
memset(fin,48,sizeof(fin));
fin[0][0]=0;
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
for(int k1=1;k1<=i;k1++)
for(int k2=1;k2<=j;k2++)
{
int pp;
if(fin[k1-1][k2-1]==fin[101][101]) continue;
for(pp=0;pp<26;pp++) if(dfs(s1,f1,pp+'a',k1,i) && dfs(s2,f2,pp+'a',k2,j)) break;
if(pp<26) fin[i][j]=min(fin[i][j],fin[k1-1][k2-1]+1);
}
printf("%d
",fin[l1][l2]==fin[101][101]?-1:fin[l1][l2]);
return 0;
}
/**
ababa
aba
2
c->ba
c->cc
*/我的码风怎么越来越奇怪了= =||