蓝桥杯不知道叫什么标题

小蓝有一个整数，初始值为1，他可以花费一些代价对这个整数进行变换。
小蓝可以花贵1的代价将教数增加1。
小蓝可以花费3的代价将整数增加一个值,这个值是整数的数位中最大的谁人(1到9) .小蓝可以花费10的代价将整数变为原来的2倍,
比方，如果整数为16花费3将整数变为22,
又如,如果整数为22花费1将整数变为33,
又如,如果整数为23,花费10将整数为 46。
叨教,如果要将整数从初始值1变为 2024，叨教限少需要多代价?
 
思路：注意！！！！只能从1开始推到2024，由于此中有一个状态方程是要求取出当前数字最大数字（1~9）,所以倒着写是不可行的。别的还要写一个函数取出当前数字内里的最大数字（1~9）。。记忆化搜索，正常写出所有推出状态的方程，并且每次要重置一个非常大的值比大小，每个状态方程的边界要写清楚。当x == 2024的时间返回0，完成基准情况即可。

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. int mem[200000];
5. int Mnum(int k)
6. {
7.         int t,M = -1e6;
8.         while(k)
9.         {
10.                 t = k % 10;
11.                 M = max(M,t);
12.                 k = k/10;
13.         }
14.         return M;
15. }
16. int dfs(int x)//当前为x数字
17. {
18.          if(x == 2024)
19.          return 0;
20.          int sum = 1e6;
21.          if(mem[x])
22.          return mem[x];
24.          if(x * 2 <= 2024)
25.          sum = min(sum,dfs(x*2)+10);
26.          
27.          if(x + Mnum(x) <= 2024)
28.          sum = min(sum,dfs(x+Mnum(x))+3);
29.          
30.          if(x + 1 <= 2024)
31.      sum = min(sum,dfs(x+1)+1);
32.      
33.          mem[x] = sum;
34.          return sum;
35. }
36. int main(void)
37. {
38.         cout << dfs(1);
39.         return 0;
40. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。