首页 > 其他分享 >dfs+剪枝

dfs+剪枝

时间:2023-03-09 12:56:28浏览次数:25  
标签:剪枝 cnt int LL dfs ans include

题目:
给定两个整数 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

相关文章

  • Middle Duplication (CFD2E) (贪心,中序树,字典序大小.dfs)
      大佬的思路:  #include<bits/stdc++.h>usingnamespacestd;intn,k,l[200010],r[200010],pos[200010];charc[200010];vector<int>seq;voidprecalc(i......
  • 天梯赛练习题L3-001 凑零钱(dfs 爆搜)
    https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805054207279104题目大意:给定n个硬币,总共需要我们凑出m块钱。问我们能凑出的硬币的最小字典序......
  • AcWing 165. 小猫爬山(dfs)
    https://www.acwing.com/problem/content/167/一共N只小猫,每个缆车最大承重量为W。N只小猫的重量分别是C1、C2……CN。当然,每辆缆车上的小猫的重量之和不能超过W。......
  • 【DFS】LeetCode 剑指 Offer 07. 重建二叉树
    题目链接剑指Offer07.重建二叉树思路递归建树,思路与【DFS】LeetCode105.从前序与中序遍历序列构造二叉树相同。代码classSolution{publicTreeNodebuild......
  • 4868. 数字替换(dfs,剪枝)
    https://www.acwing.com/problem/content/description/4871/似乎没什么好办法,只能暴搜了,bfs对于那么多状态的搜索容易tle(bfs会把所有状态都彻底搜索一遍,相比dfs不方便......
  • DFS
    DFS主要思想:1.终点,2.回溯。一、对于终点,我们要对其做一个特殊的处理也就是对结果的处理,处理完之后结束这一次的递归,即开始这一次递归的回溯二、回溯,有很多人都卡在这里。......
  • 【DFS】LeetCode 46. 全排列
    题目链接46.全排列思路本题是求排列问题.与组合问题不同的是,在排列问题中,不同的数字顺序被视为不同的排列,比如[1,2]与[2,1]是两种不同的排列。搜索树如下图所示,引......
  • 【DFS】LeetCode 90. 子集 II
    题目链接90.子集II思路去重方法与【DFS】LeetCode40.组合总和II思路相似代码classSolution{privateList<List<Integer>>result=newArrayList<>();......
  • DFS 序求 LCA
    很冷门的科技,但是有着显著的使用效果(减少建立虚树的常数)。本文学习自:Alex_Wei的博客首先遍历一遍整棵树,可以得到整棵树的DFS序和每个点的时间戳(记为\(dfn\))。考虑......
  • 【DFS】LeetCode 78. 子集
    题目链接78.子集思路求子集问题和77.组合(opensnewwindow)和131.分割回文串(opensnewwindow)又不一样了。如果把子集问题、组合问题、分割问题都抽象为一......