题目:
给定两个整数 n,x。
你可以对 x 进行任意次以下操作:
选择 x 的一位数字 y,将 x 替换为 x×y。
请你计算通过使用上述操作,将 x 变为一个 n 位数字(不含前导 0),所需要的最少操作次数。
例如,当 n=3,x=2 时,对 2 进行如下 4 次操作,即可使其变为 3 位数字:
将 2 替换为 2×2=4。
将 4 替换为 4×4=16。
将 16 替换为 16×6=96。
将 96 替换为 96×9=864。
输入格式
共一行,包含两个整数 n,x。
输出格式
一个整数,表示将 x 变为一个 n 位数字,所需要的最少操作次数。
如果无解,则输出 -1。
数据范围
所有测试点满足 2≤n≤19,1≤x<10n−1。
dfs+剪枝
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
int ans = INF;
int n;
LL x;
void dfs(LL u,int w)
{
int p[20]={0};
int cnt = 0;
LL t =u;
while(t)
{
cnt++;
p[t%10]++;
t/=10;
}
if(w>=ans) return;
if(n-cnt>=ans-w) return;
if(cnt==n&&ans>w) ans = w;
for(int i = 2;i<10;i++)
if(p[i]) dfs(u*i,w+1);
}
int main()
{
scanf("%d%lld",&n,&x);
int y = 0;
dfs(x,0);
if(ans==INF) ans = -1;
printf("%d\n",ans);
return 0;
}
标签:剪枝,cnt,int,LL,dfs,ans,include
From: https://www.cnblogs.com/freshman666/p/17197962.html