題目鏈接：http://m.shnenglu.com/Files/wwy250/problemset.rar
得分 364 用時 4h
由于做過分高一點
1.模擬沒什么說的 得分100
2.動態(tài)規(guī)劃 得分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
每次對于能直接拓展的每個節(jié)點有一個權值既通過該節(jié)點可直接拓展的節(jié)點數(shù)×一個隨機數(shù)（0<rand()<1）
從小到大一次拓展全職由小到大的節(jié)點+上一個卡時就是這個分數(shù)
5.KMP做的 得分80分
想到 AC自動機可是我只能判斷字符串集里是否有棋局的子串 而如可將所有子串求出無從下手
posted on 2009-03-09 22:09
250 閱讀(825)
評論(0) 編輯 收藏 引用 所屬分類:
oi