网站设计发展趋势,宿迁优化推广,前旗网站开发营销,百度快速优化软件小蓝有一个整数#xff0c;初始值为1#xff0c;他可以花费一些代价对这个整数进行变换。 小蓝可以花贵1的代价将教数增加1。 小蓝可以花费3的代价将整数增加一个值,这个值是整数的数位中最大的那个(1到9) .小蓝可以花费10的代价将整数变为原来的2倍, 例如#xff0c;如果整…小蓝有一个整数初始值为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完成基准情况即可。
#includeiostream
#includealgorithm
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(xMnum(x))3);if(x 1 2024)sum min(sum,dfs(x1)1);mem[x] sum;return sum;
}
int main(void)
{cout dfs(1);return 0;
}
