http://www.v2ex.com/t/65710 第一题
很简单的动态规划
分为3个原子操作: “A” | “Press Ctrl+A; Press Ctrl+C; Press Ctrl+V; Press Ctrl+V;” | "Press Ctrl+V;"
当天敲击按键x的次数的最大值为(list[x-1]+1, list[x-4] * 2, list[x-1]+copy_clipboard_num)里的最大值
当 list[x-4] * 2 与 list[x-1]+copy_clipboard_num 相等时 优先使用 list[x-4] * 2 ,这样在步数相同的情况下可以扩大clipboard 其实分析一下就可以看出PressA这种情况在第8次敲键盘之后不会出现, 也可以…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -* | |
class Operation: | |
a = "Press A;" | |
paste = "Press Ctrl+V;" | |
copy_and_paste = "Press Ctrl+A; Press Ctrl+C; Press Ctrl+V; Press Ctrl+V;" | |
def create_operation_list(): | |
operation_list = [(i, Operation.a) for i in range(0, 5)] | |
return operation_list | |
def run(press_num): | |
copy_clipboard_num = 0; | |
operation_list = create_operation_list() | |
for x in range(5, press_num+1): | |
operation_choice = max(operation_list[x-1][0] + 1, operation_list[x-4][0] * 2, operation_list[x-1][0] + copy_clipboard_num) | |
if operation_choice == operation_list[x - 4][0] * 2: | |
operation_list.append((operation_choice, Operation.copy_and_paste)) | |
copy_clipboard_num = operation_list[x - 4][0] | |
elif operation_choice == operation_list[x - 1][0] + copy_clipboard_num: | |
operation_list.append((operation_choice, Operation.paste)) | |
elif operation_choice == operation_list[x - 1][0] + 1: | |
operation_list.append((operation_choice, Operation.a)) | |
print operation_list[press_num][0] | |
if __name__ == "__main__": | |
press_num = int(raw_input()) | |
run(press_num) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment