dfs+贪心,全网最简单易懂解法

解题思路:容易想到，从高位开始遍历，最好能进行操作使其变为9（超简单贪心）。

1、遍历每一位，计算该位变为9 通过加和减两种方式的所需步数9-v[i]、v[i]+1，并与剩余A、B值进行比较。

2、若只有加操作可以得到9，则下一步只递归加操作；反之减也是一样。若两种方式均可得到，则递归2个操作

注意事项:

本题数据量小，数字最大17位，dfs深度最多18，遍历次数最多2^0+2^1+……+2^18=2^19-1，数据量符合1秒内

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans,a,b;
vector<int> v;

void dfs(int id,int va){//id表示位数下标，从高位开始遍历
	if(id==-1){//遍历完了所有数位，最低位下标为0，故为-1时得到答案
		ans=max(ans,va);return;
	}
	
	if(v[id]==9) {
		dfs(id-1,va*10+v[id]);return;
	}
	
	int f1=0,f2=0;//标志分别是否当前位可以通过加或减操作得到9
	if(a>=9-v[id]){//剩余a值 大于 通过加操作得到9的步数，则可以进行加操作
		f1=1;
	}
	if(b>=v[id]+1){//同理
		f2=1;
	}
	if(f1==1&&f2==1){//加、减操作都递归
		b-=v[id]+1;dfs(id-1,va*10+9);b+=1+v[id];
		a-=9-v[id];dfs(id-1,va*10+9);a+=9-v[id];	
		return;
	}		
	
	if(f1==1&&f2==0){//只递归加操作
		a-=9-v[id];dfs(id-1,va*10+9);a+=9-v[id]; return; 
	}
	
	if(f1==0&&f2==1){//减
		b-=v[id]+1;dfs(id-1,va*10+9);b+=v[id]+1; return; 
	}
	
	//都得不到9，那必定是只进行加操作
	int t=a;
	int ca=(v[id]+a)%10;
	a=0;
	dfs(id-1,va*10+ca);
	a=t;//变量回溯 
}
signed main(){
	
	int n;
	cin>>n>>a>>b;
	while(n){
		v.push_back(n%10);//依次存储低位-》高位
		n/=10; 
	}
	
	dfs(v.size()-1,0);
	cout<<ans;	
	return 0;
}