题目 题意:给定长度为 n n n的数组 b b b, a a a, a a a的初始值都为1,每次操作,可以选择数组 a a a的下标i和x,使得 a i = a i + ⌊ a i / x ⌋ a_i=a_i+\lfloor a_i/x \rfloor ai=ai+⌊ai/x⌋。有 k k k操作,当操作后,所有 a i = = b i a_i==b_i ai==bi的下标,可以获得硬币值 c i c_i ci,问最多能得到多少硬币。
思路:预处理1到1000,计算从1到i的需要的最少步骤次数 m n mn mn;对于值, b i b_i bi,其需要的步骤次数为 m n [ b i ] mn[b_i] mn[bi]。问题转化为,给定代价 c o s t i cost_i costi,获取值 c o i n i coin_i coini,容量为 k k k。经典01背包。由于 k < = 1000000 , n < = 1000 k