题解 P2875 【[USACO07FEB]牛的词汇The Cow Lexicon】

xlxl · 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