day35—蓝桥杯2024年第16届校赛模拟第二期-T4（最小花费）

【问题描述】

小蓝有一个整数，初始值为 1 ，他可以花费一些代价对这个整数进行变换。
小蓝可以花费 1 的代价将整数增加 1 。
小蓝可以花费 3 的代价将整数增加一个值，这个值是整数的数位中最大的那个（1 到 9）。
小蓝可以花费 10 的代价将整数变为原来的 2 倍。
例如，如果整数为 16，花费 3 将整数变为 22 。
又如，如果整数为 22，花费 1 将整数变为 23 。
又如，如果整数为 23，花费 10 将整数变为 46 。
请问，如果要将整数从初始值 1 变为 2024，请问最少需要多少代价？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;int max_digit(int n)
{int res=0;while(n){res=max(res,n%10);n/=10;}return res;
}//分离数位，返回最大值
int dp[5000];
int main()
{//dp[n]：花费// n：变化的值memset(dp,0x3f,sizeof dp);dp[1]=0;//初始条件：dp=maxfor(int i=1;i<=2050;i++){//反复遍历更新，取各自最小值即为最小花费//逻辑命题dp[i+1]=min(dp[i+1],dp[i]+1);// dp：0 1 2 3 ... //  n：1 2 3 4 ...//花费 1：累加即可//确定为：dp[2]=1dp[i+max_digit(i)]=min(dp[i+max_digit(i)],dp[i]+3);// dp：0 	3/1  6/3 ... //  n：1 	2    4 ...//确定为：dp[2]=1（更新）dp[2*i]=min(dp[2*i],dp[i]+10);//花费 10：//0 	10/1/3     ...//1 	  2        4   8 16//确定为：dp[2]=1（更新）}for(int i=0;i<2025;i++) cout<<dp[i]<<" ";//调试打印代码cout<<endl<<dp[2024]<<endl;return 0;
}