POJ3267

题目链接：http://poj.org/problem?id=3267

解题思路：

　　思路来源于网络！惭愧惭愧！

　    先dp[L] = 0。用一个循环 for(int i = L-1; i>=0; i--) 从后往前遍历 message 中的每一个字符，对于每一个 i，先让 dp[i] = dp[i+1] +1（先假设最坏的情况：在遍历到这个字符的时候无法找到匹配的字符串），然后依次遍历给出的“牛典”里面的W个单词，如果能够匹配（在 message 字符串结束之前能够找齐这个单词中的所有字母）（假设此时对于message遍历到 k），那么更新 dp[i] = min(dp[i], k-i+1-len_of_word+dp[k+1])。差不多就这样了。

AC代码：

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=600+3;
char words[maxn][30];
int len[maxn],dp[303];
char temp[303];
int main(){
    int W,L;
    scanf("%d%d",&W,&L);
    scanf("%s",temp);
    for(int i=0;i<W;i++){
        scanf("%s",words[i]);
        len[i]=strlen(words[i]);
    }
    dp[L]=0;
    for(int i=L-1;i>=0;i--){
        dp[i]=dp[i+1]+1;
        for(int j=0;j<W;j++){
            if(L-i>=len[j]){
                int ind=0;
                int k=i;
                for(;k<L;k++){
                    if(temp[k]==words[j][ind]){
                        ind++;
                        if(ind==len[j]) break;
                    }
                }
                if(ind==len[j])
                    dp[i]=min(dp[i],k-i+1-len[j]+dp[k+1]);
            }
        }
    }
    printf("%d
",dp[0]);
    return 0;
}