Skip to content

Instantly share code, notes, and snippets.

@adamwen829
Last active December 16, 2015 03:39
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save adamwen829/5371878 to your computer and use it in GitHub Desktop.
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次敲键盘之后不会出现, 也可以…
# -*- 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