USACO Feb07 奶牛詞典 Cow Lexicon

Title: 奶牛詞典

Input: lexicon.in

Output: lexicon.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★

譯: zqzas

題目描述：

沒有幾個人知道,奶牛有她們自己的字典,裡面的有W (1 ≤ W ≤ 600)個詞,每個詞的長度不超過25,且由小寫字母組成.她們在交流時,由於各種原因,用詞總是不那麼準確.比如,貝茜聽到有人對她 說"browndcodw",確切的意思是"browncow",多出了兩個"d",這兩個"d"大概是身邊的噪音.

奶牛們發覺辨認那些奇怪的資訊很費勁,所以她們就想讓你幫忙辨認一條收到的消息,即一個只包含小寫字母且長度為L (2 ≤ L ≤ 300)的字元串.有些時候,這個字元串裡會有多餘的字母,你的任務就是找出最少去掉幾個字母就可以使這個字元串變成準確的"牛語"(即奶牛字典中某些詞 的一個排列).

輸出格式:

• 第1行:兩個用空格隔開的整數,W和L.
• 第2行:一個長度為L的字元串,表示收到的資訊.
• 第3行:至第W+2行:奶牛的字典,每行一個詞.

輸出格式:

• 唯一一行:一個整數,表示最少去掉幾個字母就可以使之變成準確的"牛語".

樣例輸入:

6 10

browndcodw

cow

milk

white

black

brown

farmer

樣例輸出:

2

【分析】

這種字符串匹配問題一般都是動態規劃，如『NOIP2001 統計單詞個數』。

一開始我想了一種字符串完全匹配的方法，還想加上字典樹Trie進行優化，正在準備實現，突然發現這種算法的每一步都會產生『無窮大』的後效性，囧囧，所以果斷槍斃了這種算法。

後來又想了一個算法，狀態定義如下：

F[i] ： 對於原字符串前i個字符，最少去掉F[i]個字符就能組成『牛語』。

然後我寫了4個循環，第一個循環是枚舉"F[i]"中的那個"i".(1<=i<=L)
 第二層循環是枚舉j，第3層循環是枚舉k，使string(j+1,i)能完全包含第k個單字
第四層循環自然就是Check函數～
後來Submit，囧完了，TAAAAAAATT，Time Limit Exceeded了三組。

後來，我發現第二層、第四層循環可以合二為一，從後往前找，即從第i個字符往前，找到恰好完全包含第k個單詞的位置進行狀態轉移，很容易理解這就是最優決策。

好了，不扯了～

狀態設定：
 F[i] ： 對於原字符串前i個字符，最少去掉F[i]個字符就能組成『牛語』。 
邊界條件: F[0]=0


狀態轉移方程： F[i]=Min{F[m]+i-m-Len[k]} (Len[k]是第k個單詞的長度，m是原字符串中完全包含第k個字符串的位置的最大值)


目標狀態：F[L]


時間複雜度：O(K*L^2)


【我的代碼】
Code.1 70分

C++语言: 高亮代码由发芽网提供

01 #include <cstdio>
02 #include <cstdlib>
03 #include <cstring>
04 #include <iostream>
05 #define readfile(str) freopen(str,"r",stdin)
06 #define writefile(str) freopen(str,"w",stdout)
07 using namespace std;
08
09 char str[302];
10 char Word[601][26];
11 int W,L;
12 int Len[601];
13 int F[302];
14
15 void Back(char *s,int len)
16 {
17     for(int i=len;i>=1;i--)
18         s[i]=s[i-1];
19     s[0]='0';
20 }
21
22 void init()
23 {
24     scanf("%d %d\n",&W,&L);
25     scanf("%s\n",&str);
26     Back(str,L);
27     for(int i=1;i<=W;i++)
28     {
29         scanf("%s\n",&Word[i]);
30         Len[i]=strlen(Word[i]);
31         Back(Word[i],Len[i]);
32     }
33     return;
34 }
35
36 bool Check(int s,int e,int k)
37 {
38     int top=1;
39     int len=Len[k];
40     for(int i=s;i<=e;i++)
41     {
42         if(str[i]==Word[k][top])
43             top++;
44         if(top>len)
45             return true;
46     }
47     if(top>len)
48         return true;
49     return false;
50 }
51
52 int min(int a,int b)
53 {
54     return a>b?b:a;
55 }
56
57 void dp()
58 {
59     int Min;
60     F[0]=0;
61     bool ok;
62     for(int i=1;i<=L;i++)
63     {
64         Min=0x7fffffff;
65         for(int j=0;j<=i-1;j++)
66         {
67             for(int k=1;k<=W;k++)
68             {
69                 ok=Check(j+1,i,k);
70                 if(ok)
71                     Min=min(Min,F[j]+i-j-Len[k]);
72                 if(!ok)
73                     Min=min(Min,F[j]+i-j);
74             }
75         }
76         F[i]=Min;
77     }
78     printf("%d\n",F[L]);
79 }
80
81 int main()
82 {
83     readfile("lexicon.in"),writefile("lexicon.out");
84     init();
85     dp();
86     return 0;
87 }

Code.2 100分
裸代碼RawCode

C++语言: Codee#25416

01 /*
02 *Problem: USACO Feb07 Silver , Cow Lexicon
03 *Author : Yee-fan Zhu
04 *Method: Dynamic Programming
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 #include <cstring>
09 #include <iostream>
10 #define readfile(str) freopen(str,"r",stdin)
11 #define writefile(str) freopen(str,"w",stdout)
12 using namespace std;
13
14 char str[302];
15 char Word[601][26];
16 int W,L;
17 int Len[601];
18 int F[302];
19
20 void Back(char *s,int len)
21 {
22     for(int i=len;i>=1;i--)
23         s[i]=s[i-1];
24     s[0]='0';
25 }
26
27 void init()
28 {
29     scanf("%d %d\n",&W,&L);
30     scanf("%s\n",&str);
31     Back(str,L);
32     for(int i=1;i<=W;i++)
33     {
34         scanf("%s\n",&Word[i]);
35         Len[i]=strlen(Word[i]);
36         Back(Word[i],Len[i]);
37     }
38     return;
39 }
40
41 int min(int a,int b)
42 {
43     return a>b?b:a;
44 }
45
46 int Pipei(int s,int k)
47 {
48     int Top=Len[k];
49     for(int i=s;i>=1;i--)
50     {
51         if(str[i]==Word[k][Top])
52             Top--;
53         if(Top==0)
54             return i-1;
55     }
56     return -1;
57 }
58
59 void dp()
60 {
61     int tmp;
62     int Min;
63     F[0]=0;
64     for(int i=1;i<=L;i++)
65     {
66         Min=0x7fffffff;
67         for(int j=1;j<=W;j++)
68         {
69             tmp=Pipei(i,j);
70             if(tmp==-1)
71                 Min=min(Min,i);
72             else
73                 Min=min(Min,F[tmp]+i-tmp-Len[j]);
74         }
75         F[i]=Min;
76     }
77     printf("%d\n",F[L]);
78 }
79
80 int main()
81 {
82     readfile("lexicon.in"),writefile("lexicon.out");
83     init();
84     dp();
85     return 0;
86 }