http://poj.org/problem?id=3267

題意 ： 給你一個(gè)message，是給定字符串，然后再給你字典，讓你將message與字典中的單詞進(jìn)行匹配，輸出要?jiǎng)h掉多少字母。

思路 ： 動(dòng)態(tài)規(guī)劃問題，不僅要找對(duì)公式，還要注意一些細(xì)節(jié)問題

樣例解釋 ： 6是字典里有6個(gè)單詞，10是給定的字符串的長(zhǎng)度，給定的字符串可以與下面的brown和cow匹配，但要?jiǎng)h掉兩個(gè)字母

6 10 browndcodw cow milk white black brown farmer #include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std ; int main() {int W,L,len ;string mess,dic[40000];cin>>W>>L ;int dp[10000] ;cin>>mess ;for(int i = 0 ; i < W ; i++)cin>>dic[i] ;dp[L] = 0 ;//dp[i]代表著從i到L所要?jiǎng)h除的字符個(gè)數(shù)for(int i = L-1 ; i >= 0 ; i--)//從message中倒著找 {dp[i] = dp[i+1]+1 ;//先將最壞的可能存入數(shù)組for(int j = 0 ; j < W ; j++){len = dic[j].length() ;if(len <= L-i && dic[j][0] == mess[i])//字典里的某個(gè)單詞的長(zhǎng)度要小于你進(jìn)行匹配的一部分message的長(zhǎng)度 {int me = i,di = 0 ;while(me < L){if(dic[j][di] == mess[me++]){di++ ;}if(di == len){dp[i] = min(dp[i],dp[me]+me-i-len) ;//dp[me]代表著從me到L要?jiǎng)h除的字符的個(gè)數(shù)，me-i代表匹配過程中，從位置i到me的區(qū)間長(zhǎng)度，再減去單詞長(zhǎng)度，即可得則得到從i到me所刪除的字符數(shù)break ;}}}}}cout<<dp[0]<<endl ;return 0 ; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/luyingfeng/p/3365719.html

總結(jié)

以上是生活随笔為你收集整理的POJ3267The Cow Lexicon的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。