4868. 数字替换(dfs,剪枝)

https://www.acwing.com/problem/content/description/4871/
似乎没什么好办法,只能暴搜了,bfs对于那么多状态的搜索容易tle(bfs会把所有状态都彻底搜索一遍,相比dfs不方便剪枝,但是硬剪也可以)
但是单纯的用dfs也应该会tle,但是可以用剪枝优化
dfs优化:
1.最优化剪枝:
  (1)如果此时搜索的步数已经比临时的最小步数大了就直接return
  (2)如果已经搜索了5位,需要达到12位,至少还要乘6个数,但是相比最优解的10次还是要多,到5了就直接return
2.倒序拓展(提高搜索概率):因为要尽可能乘上大数,于是从9到2去拓展分支,尽可能提高搜索到的时间

#include<iostream>
using namespace std;
const int N = 1000;
const int INF = 1000000;
typedef long long LL;
LL x;
int n;
int res=INF;
void dfs(LL x,int step)//step步数
{
    int cnt=0;//
    bool st[10]={0};
    for( LL y=x;y>0;y/=10)cnt++,st[y%10]=true;
    if(step+n-cnt>=res)return; //最优化剪枝
    if(n == cnt)//位数相等
    {
        res=step;
        return;
    }
    for(int i=9;i>=2;i--)
        if(st[i])
            dfs(x*i,step+1);
}
int main()
{
    cin >> n >> x;
    dfs(x,0);
    if(res==INF)cout << -1 << endl;
    else cout << res << endl;
    return 0;
}