(贪心+搜索+剪枝)P8801 [蓝桥杯 2022 国 B] 最大数字

题目描述

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

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

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

你现在总共可以执行 1 号操作不超过 A 次，2 号操作不超过 B 次。

请问你最大可以将 N 变成多少?

输入格式

第一行包含 3 个整数：N，A，B 。

输出格式

一个整数代表答案。

输入输出样例

123 1 2

933

大体思路:我一开始想的是一层一层的搜索,每次都是迭代循环,然后修改了一下字符类型,搜索完成之后交了一下,60分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string s,res;
 4 int a,b;
 5 void dfs(string now,int a,int b,int num)
 6 {
 7     res=max(res,now);
 8     if(num>now.size()) return;//剪枝
 9     if(a==0&&b==0) return;//剪枝
10     while(now[num]-'0'==9) num++;//如果有9就跳过
11     if(now[num]-'0'<9)
12     {
13         if(now[num]=='0'&&b>=1) now[num]='9',dfs(now,a,b-1,num);//特判
14         else
15         {
16             if(a>=1) now[num]+=1,dfs(now,a-1,b,num),now[num]-=1;
17             if(b>=1) now[num]-=1,dfs(now,a,b-1,num),now[num]+=1;
18         }
19     }
20 }
21 int main()
22 {
23     cin>>s;
24     cin>>a>>b;
25     dfs(s,a,b,0);
26     cout<<res;
27     return 0;
28 }

很明显,由于A,B的数据范围是0-100,10x6复杂度肯定是tle了两个点,还有两个是答案错误

后来在题解中,我发现这里面的贪心思路不仅仅是每次迭代循环让数字变成9,而是一次性变,大大减小了搜索次数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string res,s;
 4 int a,b;
 5 void dfs(string now,int a,int b,int num)//现在是多少,a的次数,b的次数,现在的位置
 6 {
 7     res=max(res,now);//每次更新
 8     if((a==0&&b==0)||num==now.size()) return;//剪枝返回
 9     int u=now[num]-'0';//挑出来这次的数字
10     if(a+u>=9) now[num]='9',dfs(now,a-9+u,b,num+1);//a+u>=9的意思是,我这个位可以加一定次数可以到9,并且这个次数<=a
11     if(b>=u+1) now[num]='9',dfs(now,a,b-u-1,num+1);//与a同理
12     if(a+u<9&&b<u+1) now[num]=u+a+'0',dfs(now,0,b,num+1);//如果都不行,把这一位全加上,有可能下一位减b还会变成9,要继续搜
13 }
14 int main()
15 {
16     cin>>s>>a>>b;
17     dfs(s,a,b,0);
18     cout<<res;
19     return 0;
20 }