poj3267The Cow Lexicon(dp)

http://poj.org/problem?id=3267
dpに対して研究していないで問題の報告を見てやはり比較的に押しやすいdp[i]=min{dp[i]-1を見て、dp[j]+i-j-length[k]}Jからiまで辞書の中の単語を含みます


View Code

 1 #include <iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 using namespace std;

 6 char word[650][30];

 7 int main()

 8 {

 9     int i,j,k,n,m,dp[310],kk[610];

10     char str[310];

11     while(cin>>n>>m)

12     {

13         cin>>str;

14         memset(dp,0,sizeof(dp));

15         for(i = 1; i <= n; i++)

16         {

17             cin>>word[i];

18             kk[i] = strlen(word[i]);

19         }

20         for(i = 0 ; i < m ; i++)

21         {

22             int mi = 1000;

23             if(i>0)

24             dp[i] = dp[i-1]+1;

25             else

26             dp[i] = 1;

27             for(j = 1 ; j <= n ; j++)

28             {

29                 int g = kk[j]-1,tk = i;

30                 while(tk>=0&&g>=0&&(i-tk+1-kk[j])<dp[i])

31                 {

32                     if(str[tk]==word[j][g])

33                     g--;

34                     tk--;

35                 }

36                 if(tk<0)

37                 tk = 0;

38                 if(g<0)

39                 {

40                     mi = min(mi,i-tk-kk[j]+dp[tk]);

41                 }

42                 else

43                 mi = min(mi,i-tk+dp[tk]);

44             }

45             if(mi!=1000)

46             dp[i] = min(dp[i],mi);

47         }

48         cout<<dp[m-1]<<endl;

49     }

50     return 0;

51 }