有必要吗??
查看原帖
有必要吗??
816792
coritom楼主2024/5/19 21:02
#include <bits/stdc++.h>
using namespace std;
int a, b; 
string ans, n;
void dfs(int i, int c, int d, string s){
	if(i == n.size()){
		if(s > ans) ans = s;
		return ;
	}
	int x = s[i] - '0';
	if(x + 10 - 9 + d <= b && 9 - x + c <= a){  //如果两种操作都可以到9 
		s[i] = '9';
		dfs(i + 1, c, x + 10 - 9 + d, s);       //两种都试一下,看哪个大 
		dfs(i + 1, 9 - x + c, d, s);
	}
	else if(x + 10 - 9 + d <= b){               //只有操作1可以到9 
		s[i] = '9'; 
		dfs(i + 1, c, x + 10 - 9 + d, s);
	}
	else if(9 - x + c <= a){                    //只有操作2可以到9 
		s[i] = '9';
		dfs(i + 1, 9 - x + c, d, s);
	}
	else{                                       //把操作已用完 
		s[i] += a - c;
		dfs(i + 1, a, d, s);
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cout.tie(0), cin.tie(0);
	cin >> n >> a >> b;
	ans = n;
	dfs(0, 0, 0, n);
	cout << ans;
	return 0;
}

只需用来一波贪心就行,都不需要数位dp。

2024/5/19 21:02
加载中...