BZOJ 1633 [Usaco2007 Feb]The Cow Lexicon 牛的词典（单调DP）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1633
【题目大意】
给出一个字符串和一个字符串集，
问要删去多少个字符该字符串才可以被字符串集完全表示
【题解】
dp[i]表示长度为i时候的答案，单调dp即可
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1010;
char s[N],c[N][35];
int n,len,k,dp[N];
int main(){
scanf("%d%d %s",&n,&len,s+1);
for(int i=1;i<=n;i++)scanf("%s",c[i]+1);
for(int i=1;i<=len;i++){
dp[i]=i;
for(int j=1;j<=n;j++){
int l=strlen(c[j]+1),cnt=0;
for(k=i;k;k--){
if(c[j][l]==s[k])l--;
else cnt++;
if(!l)break;
}if(!l)dp[i]=min(dp[i],dp[k-1]+cnt);
}
}printf("%d
",dp[len]);
return 0;
}