蓝桥杯国赛（最大数字）

本文主要是介绍蓝桥杯国赛（最大数字），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：

本题是一个典型的回溯问题，en.....题主最开始以为是一个贪心，贪心写的代码只通过了60%qvq 

题目描述：

 思路：

本题用回溯去查找先对操作1查找再回溯对操作2查找

AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
char n[20];
int a, b;
long long maxx;//记录最终答案
void dfs(int i, long long sum) {  //因为题上数据范围到1e17，所以不开long long见祖宗嗷if (n[i] == '\0') {maxx = max(maxx, sum);    //一次查找完毕，进行比较return;}else {int x = n[i] - '0';    //转为intint c = min(a, 9 - x);   //看a的剩余值a -= c;dfs(i + 1, sum * 10 + c + x);   //递归查找a += c;    //操作1的回溯if (b >= x + 1) {     //如果不能将数减到9，我们不应进行操作2b -= (x + 1);dfs(i + 1, sum * 10 + 9);   //递归查找b += x + 1;      //操作2的回溯}}
}
int main() {scanf("%s %d %d", n, &a, &b);dfs(0, 0);      //初始的i和sum均应为0cout << maxx;return 0;
}

这篇关于蓝桥杯国赛（最大数字）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---