Kickstart Round E 2017

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_)))))