題目鏈接：http://www.shnenglu.com/Files/wwy250/problemset.rar
得分 364 用時 4h
由于做過分高一點
1.模擬沒什么說的 得分100
2.動態規劃 得分100
令f[c][l]=為匹配部分為字符串c的前綴l使得后面的字符串有
兩種分解方法的最小長度
這句話說的我自己都聽不懂請大家結合下圖看
所以答案即為min(f[i][0]|1<=i<=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的子串))
至于輸出方案就不用我說了吧
3.按N皇后搜的 得分30
4.貪心+隨機化+卡時 得分54
每次對于能直接拓展的每個節點有一個權值既通過該節點可直接拓展的節點數×一個隨機數（0<rand()<1）
從小到大一次拓展全職由小到大的節點+上一個卡時就是這個分數
5.KMP做的 得分80分
想到 AC自動機可是我只能判斷字符串集里是否有棋局的子串 而如可將所有子串求出無從下手
posted on 2009-03-09 22:09
250 閱讀(829)
評論(0) 編輯 收藏 引用 所屬分類:
oi