问题分析

这道题属于贪心加回溯。所有操作如果能使得高位的数字变大必定优先用在高位，因为对高位的影响永远大于对低位的影响。然后我们再来分析一下，如何使用这两种操作？对于加操作，如果能使这一位的数字加到9则变成9，否则使这个数字尽量大。对于减操作，如果能使这一位的数字减到9则变成9，否则不采用减操作。然后我们用回溯来分别对该位进行加操作和减操作，记录最大值。时间复杂度大概是$O(2^{l{g}^n})$,不超过$10^4$的数量级。因此回溯是可行的。

AC_Code

#include <bits/stdc++.h>
using namespace std;
string result;
void dfs(string str,int i,int a,int b){
	if(i==str.size()||a==0&&b==0){
		if(result<str){
			result=str;
		}
		return;
	}
	char ch=str[i];
	if('9'-ch<=a){//能加到9 
		str[i]='9';
		dfs(str,i+1,a-('9'-ch),b);
	}else{//不能加到9 
		str[i]=ch+a;
		dfs(str,i+1,0,b);
	}
	if((ch-'0'+1)<=b){//能减到9 
		str[i]='9';
		dfs(str,i+1,a,b-(ch-'0'+1));
	}else{//不能减到9 
		str[i]=ch;
		dfs(str,i+1,a,b); 
	}
}
int main() {
	string str;
	int a,b;
	cin>>str>>a>>b;
	dfs(str,0,a,b);
	cout<<result<<endl;
	return 0;
}