免费中文网站模板,买网站空间需要知道的,公众号制作教程视频,凤岗网站建设公司题意#xff1a;就是给出一个主串#xff0c;和一本字典#xff0c;问最少在主串删除多少字母#xff0c;可以使其匹配到字典的单词序列。 PS:是匹配单词序列#xff0c;而不是一个单词。 f[i]表示从message中第i个字符开始#xff0c;到第L个字符#xff08;结尾处就是给出一个主串和一本字典问最少在主串删除多少字母可以使其匹配到字典的单词序列。 PS:是匹配单词序列而不是一个单词。 f[i]表示从message中第i个字符开始到第L个字符结尾处这段区间所删除的字符数初始化为f[L]0 由于我的程序是从message尾部向头部检索匹配所以是下面的状态方程 1、f[i]f[i1]1 不能匹配时最坏情况 2、f[i]min(f[i],f[p](p-i)-q) 可以匹配时取最优 // Time 94ms; Memory 268K#includeiostream
using namespace std;
int main()
{int w,l,i,j,p,q;char m[305],d[605][30];int f[305];cinwl;cinm;for(i0;iw;i)cind[i];f[l]0;for(il-1;i0;i--){f[i]f[i1]1;for(j0;jw;j) if(m[i]d[j][0]){pi;q0;while(pl){if(m[p]d[j][q]){q;if(d[j][q]0) break;}p;}if(pl f[i]f[p]p-i-q) f[i]f[p]p-i-q;}}coutf[0]endl;return 0;
} 转载于:https://www.cnblogs.com/java20130726/p/3218211.html
