这个做法用了38ms，比y总慢。
看到第一眼，嗯~ o(￣▽￣)o，迭代加深，然后按着这个思路往下打，T飞了。
然后加了几个优化，过了？？？？
首先还是那个迭代加深，但是我们还要加几个优化。
未用到的优化：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 40
using namespace std;
inline int zabs(int x){return x<0?-x:x;}
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
char st[20][N],ed[N];int v[20][N];
int n,m;
struct CHANGE
{
char a[N],b[N];
int alen,blen,score_cha;
}ch[10];int top,ed_score;
inline bool cmp(CHANGE x,CHANGE y){return x.score_cha>y.score_cha;}
inline int getscore(char *a,int len)//获取每个字符串的sum值
{
int ans=0;
for(int i=1;i<=len;i++)ans+=a[i];
return ans;
}
inline bool comp(char *a,char *b,int len)
{
for(int i=1;i<=len;i++)
{
if(a[i]!=b[i])return 0;
}
return 1;
}
inline bool pd(int *a,int len,int ti)
{
for(int i=1;i<=len;i++)
{
if(a[i]==ti)return 1;
}
return 0;
}
inline bool check_dfs(int dep,int val,int res)
{
if(!val)return 1;
if(dep>top)return 0;
if(dep>1 && ch[dep].score_cha==ch[dep-1].score_cha)return check_dfs(dep+1,val,res);
for(int i=0;i<=res;i++)if(check_dfs(dep+1,val+ch[dep].score_cha*i,res-i)==1)return 1;
return 0;
}
inline bool check(int val,int cnt/*剩余步数*/){return check_dfs(1,val,cnt);}
int limit;
bool dfs(int dep,int ti/*时间戳*/,int pre,bool bk)
{
if(strlen(ed+1)==strlen(st[dep]+1) && comp(ed,st[dep],strlen(ed+1)))return 1;
if(bk/*判断这个字符串是不是跑过了*/ && !check(getscore(st[dep],strlen(st[dep]+1))-ed_score,limit-dep))return 0;
int now=strlen(st[dep]+1);
for(int i=1;i<=top;i++)
{
int ed=now-ch[i].alen+1;
for(int j=pre;j<=ed;j++)
{
if(comp(st[dep]+j-1,ch[i].a,ch[i].alen)==1 && pd(v[dep]+j-1,ch[i].alen,ti)==1)
{
memset(st[dep+1],0,sizeof(st[dep+1]));
for(int t=1;t<j;t++)st[dep+1][t]=st[dep][t];
for(int t=1;t<=ch[i].blen;t++)st[dep+1][j-1+t]=ch[i].b[t];
for(int t=j+ch[i].alen;t<=now;t++)st[dep+1][t-ch[i].alen+ch[i].blen]=st[dep][t];
memset(v[dep+1],0,sizeof(v[dep+1]));
for(int t=1;t<j;t++)v[dep+1][t]=v[dep][t];
for(int t=1;t<=ch[i].blen;t++)v[dep+1][j-1+t]=ti+1;
for(int t=j+ch[i].alen;t<=now;t++)v[dep+1][t-ch[i].alen+ch[i].blen]=v[dep][t];
if(dfs(dep+1,ti,j+ch[i].blen,1)==1)return 1;
}
}
}
//我们把时间戳加加
if(pre!=1)return dfs(dep,ti+1,1,0);
return 0;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%s%s",st[0]+1,ed+1);ed_score=getscore(ed,strlen(ed+1));
while(scanf("%s%s",ch[top+1].a+1,ch[top+1].b+1)!=EOF)
{
top++,ch[top].alen=strlen(ch[top].a+1),ch[top].blen=strlen(ch[top].b+1);
ch[top].score_cha=getscore(ch[top].b,ch[top].blen)-getscore(ch[top].a,ch[top].alen);
}
sort(ch+1,ch+top+1,cmp);//排序只是为了方便check_dfs中的ch[dep].score_cha==ch[dep-1].score_cha判断
for(int i=1;i<=10;i++)
{
limit=i;
if(dfs(0,0,1,1)==1)
{
printf("%d\n",i);
return 0;
}
}
printf("NO ANSWER!\n");
return 0;
}
那么有人会问：\(check\)_\(dfs\)这个函数会不会特别慢呢？
其实不会，我们讨论函数状态\((i,j)\)，表示第\(i\)层，并且位于第\(j\)个规则，要么\(j++\)，要么\(i++\)，所以时间复杂度：\(C_{16}^6=8008\)
其实还是很大
但事实上，你可以选择在\(dep\)大一点的时候执行\(check\)函数，例如，如果\(cnt>=1\)再执行，就会变成：\(C_{15}^6=5005\)，合理选择，反正数据弱。
当然，还有可以优化的地方，看这个：
inline int getscore(char *a,int len)//获取每个字符串的sum值
{
int ans=0;
for(int i=1;i<=len;i++)ans+=a[i];
return ans;
}
当你把\(a[i]\)换成\(a[i]-‘a‘+1\)时会在最后一个点光荣去世，T到爆炸，为什么，因为：\(1+1=2\)啊，也就是说\("aa"="b"\)，啊这。。。。
再看看原来：\(98-97=1\)，在不相同的长度下，在不同的长短下，基本上是不会相同的，也就是隐含了长度信息。（但实际上这道题目其实不止小写字母，所以他用一些神奇的符号，也是可以让我们的\(sum\)不再包含位置信息的，或者专门卡差值也是可以的，但是我们只要给每一个位置加上一个较大的数字就可以了。）
继续深入的思考，那么在相同的长度下呢？
\("ad=bc"\)？不难发现，这个我们是可以解决的，怎么解决？我们只要把\(a[i]\)换成\(a[i]*a[i]\)即可，当然这样子干说不定会出一些其他问题（时间问题，不是答案问题），比如原本\("at"≠"bd"\)，但是现在等于了（只是单纯的举个例子，现实中不一定相等），这样子搞就想Hash一样，让出题人更难卡，但是减慢了随机数据的速度。
那有没有究极的优化方法呢？
有，前提是要加上长度变量判断，我们为什么会怕\("ad"="bc"\)，还不是因为每一个字母的区分度是在是太小了，所以我们要是用一个更有区分度的方法就好了，例如上文的\(a[i]^2\)，当然，我们直接弄成\(\%\)意义下的\(2^{a[i]}\)次幂，这样区分度绝对很高。这不就是Hash吗。
但实际上，不管怎么优化，都优化不了一个软肋，就是：\("ab"="ba"\)，他是我们这个数值判断最大的弊端，也是很难被改动的，因为这就是这个优化根本上存在的问题，但是速度已经够快了，不管他了。
但是由于是玄学的判断，实际效果好不好我是真的不知道，反正不加也能A
原文：https://www.cnblogs.com/zhangjianjunab/p/13762363.html