題目鏈接：http://www.shnenglu.com/Files/wwy250/problemset.rar
得分 364 用時(shí) 4h
由于做過(guò)分高一點(diǎn)
1.模擬沒(méi)什么說(shuō)的 得分100
2.動(dòng)態(tài)規(guī)劃 得分100
令f[c][l]=為匹配部分為字符串c的前綴l使得后面的字符串有兩種分解方法的最小長(zhǎng)度
這句話說(shuō)的我自己都聽不懂請(qǐng)大家結(jié)合下圖看

所以答案即為min(f[i][0]|1<=i<=n)
轉(zhuǎn)移方程為：f[c][l]=min(min(getf(i,strlen(s[c])-l)+l|后綴l+1為i的子??? 串),min(getf(c,l+strlen(s[i]))|i為后綴l+1的子串))
至于輸出方案就不用我說(shuō)了吧
3.按N皇后搜的 得分30
4.貪心+隨機(jī)化+卡時(shí) 得分54
每次對(duì)于能直接拓展的每個(gè)節(jié)點(diǎn)有一個(gè)權(quán)值既通過(guò)該節(jié)點(diǎn)可直接拓展的節(jié)點(diǎn)數(shù)×一個(gè)隨機(jī)數(shù)（0<rand()<1）
從小到大一次拓展全職由小到大的節(jié)點(diǎn)+上一個(gè)卡時(shí)就是這個(gè)分?jǐn)?shù)
5.KMP做的 得分80分
想到 AC自動(dòng)機(jī)可是我只能判斷字符串集里是否有棋局的子串 而如可將所有子串求出無(wú)從下手