蓝桥杯不知道叫什么题目

小蓝有一个整数，初始值为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，完成基准情况即可。

#include<iostream>
#include<algorithm> 
using namespace std;
int mem[200000];
int Mnum(int k)
{
int t,M = -1e6;
while(k)
{
t = k % 10;
M = max(M,t);
k = k/10;
}
return M;
}
int dfs(int x)//当前为x数字 
{
 if(x == 2024)
 return 0;
 int sum = 1e6;
 if(mem[x])
 return mem[x];

 if(x * 2 <= 2024)
 sum = min(sum,dfs(x*2)+10);
 
 if(x + Mnum(x) <= 2024)
 sum = min(sum,dfs(x+Mnum(x))+3);
 
 if(x + 1 <= 2024)
     sum = min(sum,dfs(x+1)+1);
     
 mem[x] = sum;
 return sum;
}
int main(void)
{
cout << dfs(1);
return 0;
}

原文地址：https://blog.csdn.net/zqystca/article/details/144012291

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！