题目
做法
这个做法用了38ms，比y总慢。
看到第一眼，嗯~ o(￣▽￣)o，迭代加深，然后按着这个思路往下打，T飞了。
然后加了几个优化，过了？？？？
首先还是那个迭代加深，但是我们还要加几个优化。
- 减少重复搜索。
看这个规则：$a->b$，还有字符串：$aa????$，那么他很有可能会重复搜索，所以我们要通过指定搜索顺序的方法来减少重复，有人问，不是加个$pre$变量储存上一次时在哪个地方变化不就行了？但是有的时候使用这个规则是在某个规则用了的情况下实施的，所以就不行了（如：$a->b,b->c$）。
所以我们需要开一个$v$数组，记录时间戳，依旧是$pre$，在这一层中我们就按照$pre$不断往后，同时有一个要求，就是被替换的区间当中一定要有一个$v$等于当前时间戳，具体实现看下面的代码。 - 可行性判断优化
我们可以对一个字符串加上他们的ASCII码，记为这个字符串的$sum$值，然后用一个$check$判断在经过若干次规则后能不能等于$ed$的$sum$值。
未用到的优化：
1. Hash（字符串匹配）加前缀和优化（$v$数组部分判断区间是否有相等的时间戳），但因为常数较大，且$check$用时更长，故不加。
2. 在check函数中，加上长度这个变量，但是因为懒得打，所以没加。
#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
