https://code.google.com/codejam/contest/12234486/dashboard#s=a
https://zhuanlan.zhihu.com/p/28829564
Problem A. Copy & Paste
肯定是DP了，要知道转移状态肯定要包含buffer里面是什么string，
不好确定这个string是什么！到这里有点卡住了。
其实有个套路的，不知道是什么，枚举一下就好了，反正就N^2个，N也不是很大
最近怎么感觉可以根据数据的大小来判断可能用什么方法？
import sys
out_to_file = []
def slove(s):
# no words in clipboard is not considered in dp array
dp=[[[999999 for _ in range(len(s)+1)] for _ in range(len(s))] for _ in range(len(s))]
dp[0][0][1] = 2
# no words in clipboard is considered in dp array
mi = [i+1 for i in range(len(s))]
for i in range(0, len(s)-1):
# only loop for valid substring
for j in range(i+1):
for k in range(j+1, i+2):
dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]+1)
mi[i+1] = min(mi[i+1], dp[i+1][j][k])
if s[i+1:].startswith(s[j:k]):
dp[i+k-j][j][k] = min(dp[i+k-j][j][k], dp[i][j][k]+1)
dp[i+k-j][j][k] = min(dp[i+k-j][j][k], mi[i]+2)
mi[i+k-j] = min(mi[i+k-j], dp[i+k-j][j][k])
return min(len(s), mi[len(s)-1])
sys.stdin = open('submit.in', 'r')
cases = int(input())
for i_ in range(cases):
print(i_)
s=input()
out_to_file.append(slove(s))
fp = open('submit.out', 'w')
for i_,c_ in enumerate(out_to_file):
fp.write('Case #%d: %s\n'%(i_+1, str(c_)))
# fp.write('Case #%d: %s\n'%(i_+1,' '.join(list(map(str,c_)))))
