AcWing 第 93 场周赛 4868. 数字替换（dfs+剪枝）

https://www.acwing.com/problem/content/4871/

题目大意：

给定两个整数 n,x。（x为原始数据，n为需要我们把x变成的位数）

可以对x进行任意次以下操作：

选择x的一位数字y，将x替换为x*y。

求出把x变成n位数的最小操作数，如果无法达到，输出-1.

扩展数据
输入
5 403
输出
2

有很多年度迷惑大bug，为啥LL mp[10]；提成全局这个扩展数据就输出3了？？？
我不李姐（抓狂，这个点找了快1个小时

写法一

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=9e18,MINN=-1e18;
const LL N=1e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL n,x,minn=MAXN;
void dfs(LL xx,LL sum)
{
    string sx=to_string(xx);
    //cout<<sx<<endl;
    if(sx.size()>n) return ;
    if(sx.size()==n)
    {
        minn=min(minn,sum);
        return ;
    }
    //如果当前已经积累的位数+还需要凑满的位数>=目前我已经获得过的最小值
    //就没有重复的必要了
    if(sum+n-sx.size()>=minn) return ;
    LL mp[10];
    for(int i=0;i<10;i++)
        mp[i]=0;
    for(LL i=0;i<sx.size();i++)
    {
        mp[sx[i]-'0']=1;
    }
    for(int i=9;i>1;i--)
    {
        if(mp[i]) dfs(xx*i,sum+1);
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>x;
        dfs(x,0);
        if(minn==MAXN) cout<<"-1"<<endl;
        else cout<<minn<<endl;
    }
    return 0;
}

写法二

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=9e18,MINN=-1e18;
const LL N=1e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL n,x;
LL minn=MAXN;
LL get(LL num)
{
    LL res=0;
    while(num)
    {
        res++;
        num/=10;
    }
    return res;
}
void dfs(LL xx,LL sum)
{
    LL t=get(xx);
    if(t>n) return ;
    if(t==n)
    {
        minn=min(minn,sum);
        return ;
    }
    if(sum+n-t>=minn) return ;
    LL mp[10];
    for(int i=0;i<10;i++)
        mp[i]=0;
    LL flag=xx;
    while(flag)
    {
        mp[flag%10]=1;
        flag/=10;
    }
    for(int i=9;i>1;i--)
    {
        if(mp[i]) dfs(xx*i,sum+1);
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>x;
        dfs(x,0);
        if(minn==MAXN) cout<<"-1"<<endl;
        else cout<<minn<<endl;
    }
    return 0;
}