DFS 蓝桥杯

最大数字

问题描述

给定一个正整数 NN 。你可以对 NN 的任意一位数字执行任意次以下 2 种操 作：

1. 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。

2. 将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。

你现在总共可以执行 1 号操作不超过 AA 次, 2 号操作不超过 BB 次。 请问你最大可以将 NN 变成多少?

输入格式

第一行包含 3 个整数: N,A,BN,A,B 。

输出格式

一个整数代表答案。

dfs流程

void dfs(int u) //u表示到第几位
{if() {return;}  //边界st[i] = 1; // 改变条件dfs(u + 1); //下一步st[i] = 0; // 恢复现场}

代码（通过率40%）

#include <bits/stdc++.h>
using namespace std;#define int long long
string n;
int a, b;
int l,mx,res;void dfs(int u)
{if(u == l) {mx = max(mx, res);cout << mx;return;}int t = n[u];int x = min(9-t, a);a-=x;res = res*10 + t + x; dfs(u+1);a+=x;if(b > t) {b-=(t+1);res = res*10 + 9;dfs(u+1);b+=t+1;}
}signed main()
{// 请在此输入您的代码cin >> n >> a >> b;l = n.size();  dfs(0);  return 0;
}

ac代码

#include <iostream>
#include <cmath>
using namespace std;
string n;
long long ans; 
int a,b;
void dfs(int x,long long an){    //a代表每次遍历的数 int t=n[x]-'0';    //位数转为intif(n[x]){          //防止为空 int c=min(a,9-t);a-=c;dfs(x+1,an*10+t+c);a+=c;if(b>t){b=b-t-1;dfs(x+1,an*10+9);b=b+t+1;}}else{ans=max(ans,an);}
}
int main(){cin>>n>>a>>b;dfs(0,0);   //0号字符 cout<<ans;return 0;
}