准备给新生上课的ppt好花时间。
给一个长字符串和一个字典，问字符串中最少删除多少个字符，剩下的串可以由字典中的单词不重叠拼成。
Input
Line 1: Two space-separated integers, respectively:
W and
L
Line 2: L characters (followed by a newline, of course): the received message
Lines 3.. W+2: The cows' dictionary, one word per line
Line 2: L characters (followed by a newline, of course): the received message
Lines 3.. W+2: The cows' dictionary, one word per line
Output
Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.
这个题不难但是我用了好几种奇怪的姿势最后看题解才做出来，一维DP，dp[i]表示从i到长串末尾最少删多少个字符满足条件，递推是这样的：
dp[i]=min( dp[i+1], dp[tem]+tem-i-tlen )
dp[i+1]是说如果舍弃i位置的字符；tem是尝试从i开始匹配一个单词，一旦匹配成功就记录tem为成功时长串的位置，tlen是匹配的字典中单词的长度。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
#define mxl 310
#define mxw 610
char a[mxl];
char word[mxw][30];
int w,l;
int dp[mxl];
int main(){
while(scanf("%d%d",&w,&l)!=EOF){
scanf("%s",a);
for(int i=0;i<w;++i)
scanf("%s",word[i]);
dp[l]=0;
for(int i=l-1;i>=0;--i){
dp[i]=dp[i+1]+1;
int cur1,cur2,teml;
for(int j=0;j<w;++j) if(word[j][0]==a[i]){
cur1=i,cur2=0,teml=strlen(word[j]);
while(cur2!=teml&&cur1!=l){
if(a[cur1]==word[j][cur2])
++cur2;
++cur1;
}
if(cur2==teml) dp[i]=min(dp[i],dp[cur1]+cur1-teml-i);
}
}
printf("%d\n",dp[0]);
}
return 0;
}