模拟赛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
    
     #include
     
      #include
      
       #include
       
        #define inf 20021225#define ll long longusing 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
        
         '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\n",fin[l1][l2]==fin[101][101]?-1:fin[l1][l2]);	return 0;}/**ababaaba2c->bac->cc*/
        
       
      
     
    

我的码风怎么越来越奇怪了= =||