感觉有点像是被卡常了，记忆化的时候把现有操作数和记录操作数比较的符号从大于改成大于等于了后，只tle俩了，虽然说还是比bfs慢太多吧，我不理解
by xiaohai1 @ 2023-12-15 02:24:28
贴个代码：
```
#include <bits/stdc++.h>
using namespace std;
long long s,m,ans[100005],maxw;
long long qnum(long long x,long long a)
{
return (x/(long long)pow(10,a-1))%10;
}
long long change(long long a,long long b,long long x)
{
long long q=x,numa,numb;
numa=qnum(x,a);
numb=qnum(x,b);
return q+(numa-numb)*pow(10,b-1)+(numb-numa)*pow(10,a-1);
}
long long cut(long long x,long long a)
{
long long q=x%(long long)pow(10,a-1);
q+=(long long)(x/(long long)pow(10,a))*(long long)pow(10,a-1);
return q;
}
long long inc(long long x,long long a,long long tot)
{
long long q=x%(long long)pow(10,a);
q+=(long long)(x/(long long)pow(10,a))*(long long)pow(10,a+1);
return q+(qnum(x,a+1)+tot)*pow(10,a);
}
void dfs(long long x,long long num)
{
if(ans[x]!=-1&&num>=ans[x]&&x!=s)
{
return;
}
ans[x]=num;
for(long long i=1;i<=log10(x)+1;i++)
{
dfs(cut(x,i),num+1);
}
if(log10(x)+1<maxw)
{
for(long long i=1;i<=log10(x);i++)
{
if(qnum(x,i)>qnum(x,i+1))
{
long long tot=qnum(x,i)-qnum(x,i+1)-1;
while(tot)
{
dfs(inc(x,i,tot),num+1);
tot--;
}
}
}
}
for(long long i=1;i<=log10(x);i++)
{
for(long long j=i+1;j<=log10(x)+1;j++)
{
dfs(change(i,j,x),num+1);
}
}
return;
}
int main()
{
memset(ans,-1,sizeof(ans));
cin>>s>>m;
ans[s]=0;
maxw=log10(s)+1;
dfs(s,0);
for(long long i=1;i<=m;i++)
{
long long x;
cin>>x;
cout<<ans[x]<<endl;
}
return 0;
}
```
by xiaohai1 @ 2023-12-15 02:26:28
每个数真的只会被搜一遍吗？
比如说你 $12359$ 在步数为 $14$ 的时候搜了一遍，然后你另一次 DFS 的时候步数是 $13$，不还要重新搜一遍吗？
by yummy @ 2023-12-15 08:11:51
管理楼下
by Zachary_zhong @ 2024-01-26 17:13:08