一维数轴,初始位置在原点,每次可以选择向左或者向右移动0或3或7或11个单位
N次询问,每次给出一个坐标arr[i],求从0点走到arr[i]需要的最少次数
[1,4,14]
[3,2,2]
从0到1最少需要3次(0->7->4->1)(走法不唯一,比如0->11->4->1也只需要3次)从0到4最少需要2次(0->7->4)从0到14最少需要2次(0->7->14)
[6,25]
[2,3]
从0到6最少需要2次(0->3->6)从0到25最少需要3次(0->7->18->25)
对于20%的数据
对于50%的数据
对于100%的数据
def solve_2(self, arr): # dp_init = self.__solve_table(100) dp_init = [0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3] max_num = max(arr) dp = [0 for i in range(max_num + 1)] # 初始化 for i in range(1, 12): dp[i] = dp_init[i] # 动态转移方程 # dp[i] = min(dp[i-11], dp[i-7], dp[i-3]) + 1 for i in range(12, max_num + 1): dp[i] = min(dp[i - 11], dp[i - 7], dp[i - 3]) + 1 rnt = list() for i in arr: rnt.append(dp[i]) return rnt
def solve_3(self, arr): # dp_init = self.__solve_table(100) dp_init = [0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3] max_num = max(arr) dp = [0 for i in range(15)] # 初始化 middle = dict() for i in range(1, 12): dp[i] = dp_init[i] if i in arr: middle[i] = dp[int(i % 12)] # 动态转移方程 + 循环数组 # dp[i] = min(dp[i-11], dp[i-7], dp[i-3]) + 1 j, a, b, c = 0, 1, 5, 9 arr_set = set(arr) for i in range(12, max_num + 1): # j = int(i % 12) # dp[j] = min(dp[j - 11], dp[j - 7], dp[j - 3]) + 1 # dp[j] = min(dp[int((i - 11) % 12)], dp[int((i - 7) % 12)], dp[int((i - 3) % 12)]) + 1 dp[j] = min(dp[a], dp[b], dp[c]) + 1 if i in arr_set: middle[i] = dp[j] j, a, b, c = int((j + 1) % 12), int((a + 1) % 12), int((b + 1) % 12), int((c + 1) % 12) rnt = list() for i in arr: rnt.append(middle[i]) return rnt
def solve_4(self, arr): """ 找规律 0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3, 4, 5, 4, 3, 4, 5, 4, 3, 6, 5, 4, 5, 6, 5, 4, 5, 6, 5, 4, 7, 6, 5, 6, 7, 6, 5, 6, 7, 6, 5, 8, 7, 6, 7, 8, 7, 6, 7, 8, 7, 6, 9, 8, 7, 8, 9, 8, 7, 8, 9, 8, 7 """ # dp_init = self.__solve_table(100) dp_init = [0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3] rnt = list() for num in arr: if num < len(dp_init): rnt.append(dp_init[num]) continue tmp = int(num % 11) if tmp == 0: rnt.append(num // 11) continue if tmp in [3, 7]: rnt.append(num // 11 + 1) continue if tmp < 3: rnt.append(num // 11 + 4 - tmp) elif tmp == 4: rnt.append(num // 11 + 2) elif tmp == 5: rnt.append(num // 11 + 3) elif tmp == 6: rnt.append(num // 11 + 2) elif tmp == 8: rnt.append(num // 11 + 2) elif tmp == 9: rnt.append(num // 11 + 3) elif tmp == 10: rnt.append(num // 11 + 2) return rnt