dfs80分,30行代码求调
查看原帖
dfs80分,30行代码求调
1266423
yjjimpaopao楼主2024/11/4 13:32
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
int add_cost[20];
int sub_cost[20];
int d_max[20];
string str;
int n[20];
int a;
int b;
void dfs(int d, int na, int nb) { //(当前数位,剩余增加次数,剩余减少次数)
	if (d == str.length()) return;//递归结束
	if (na < add_cost[d] && nb < sub_cost[d]) {
		d_max[d] = max(d_max[d], n[d] + na); //无法到达9时,该位的最大数字
		dfs(d + 1, 0, nb); //+1次数用完
	}
	else {
		d_max[d] = 9;
		if (na >= add_cost[d]) dfs(d + 1, na - add_cost[d], nb);
		if (nb >= sub_cost[d]) dfs(d + 1, na, nb - sub_cost[d]);
	}
}
int main(void)
{
	cin >> str >> a >> b;
	for (int i = 0; i < str.length(); i++)
	{
		n[i] = str[i] - '0';
		add_cost[i] = 9 - n[i];
		sub_cost[i] = (n[i] + 1) % 10;
	}
	dfs(0, a, b);
	for (int i = 0; i < str.length(); i++)
	{
		cout << d_max[i];
	}
	return 0;
}
2024/11/4 13:32
加载中...