自动搬运

查看原文

来自洛谷，原作者为

	xlxl AFO..

搬运于2025-08-24 21:42:33，当前版本为作者最后更新于2020-01-19 15:05:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

顶重要的东西：dp[i] 表示前i个字符去掉多少个为最优解

初始值：dp[i]=i;(1~n)

目标值：dp[len]

扔代码（有注释）~~

#include<bits/stdc++.h> 
using namespace std;
int n,len1,dp[310];
char s[310],c[610][310];
int main(){
    cin>>n>>len1>>s+1;
	//输入:字典词数n   交流长度len1   交流语言s+1 
    for(int i=1;i<=n;i++)
		cin>>c[i]+1;
	//输入字典内容
	//注意！！字符串从0开始 
    for(int i=1;i<=len1;i++){//遍历交流语言 
        dp[i]=i;//全去掉一定可以 
        for(int j=1;j<=n;j++){//遍历字典内容 
            int len2=strlen(c[j]+1);//取字典中每一个词的长度 
            int cnt=0,k;
            //cnt删去个数清零 
            for(k=i;k>=1;k--){//从后往前遍历字典是否相符 
                if(c[j][len2]==s[k])//判断 
					len2--;
                else 
					cnt++;//计数器 
                if(len2==0)//这个词结束 
					break;
            }
            if(k!=0)//这个词结束（以防止切一半） 
				dp[i]=min(dp[i],dp[k-1]+cnt);//更新dp值 
        }
    }
    cout<<dp[len1];
    return 0;
}

就这样。。没了（感觉很简单）

真那样你就不会看到我的题解了^~^

最后一句话————poj3267见.BYE