即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

统计单词个数

编程语言 qq_35914587 15℃ 0评论

QAQ


话说这个题目跟那个乘号的比较像啊,,,,,,,


用f[i][j]表示前i个字母划分为j段的单词最大数


那么我们很容易就得到一个状态转移方程


f[i][j]=max(f[i][j],f[l-1][j]+w)//w为l-i区间里单词的数目


现在的问题是w咋求


之前我做的一个题是划分乘号的


那个我们处理了一个sum[i][j]数组,表示的是i-j组成的数字


这个题目可以这样处理,但是还有个跟巧妙的方法


处理一个d[i]数组,表示以i为首位置的单词的终点,这个距离肯定越小越好


这样我们再倒着枚举,就可以达到一个很好地效果

#include 
#include 
#include 
#include 
using namespace std;
char s[99999];
char sn[8][999],len[8]; 
int d[9999];//以i为首位置的单词的终点 
int dp[999][999];//前i个字母划分为j段的单词最大数 
int p,m;    
int t;
int screen()
{
    int n=strlen(s+1);
    memset(d,127,sizeof(d));

    for(int i=1;i<=n;i++)
     for(int j=1;j<=t;j++)
      {
        if(n-i+1continue;
        int flag=0;
        for(int l=0;lif(s[i+l]!=sn[j][l+1]) 
         {
            flag=1;
            break;
         }
         if(flag) continue;
         d[i]=min(d[i],i+len[j]-1);

      }  

    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
        int sum=0;
        for(int l=i;l>=j;l--)
        {

        if(d[l]<=i) sum++;
        dp[i][j]=max(dp[i][j],dp[l-1][j-1]+sum);
        }
     }


     return dp[n][m];
}
int main()
{
    scanf("%d%d",&p,&m);

    for(int i=1;i<=p;i++)
     scanf("%s",s+1+(i-1)*20);

    scanf("%d",&t);

    for(int i=1;i<=t;i++)
     scanf("%s",sn[i]+1),len[i]=strlen(sn[i]+1);

    printf("%d",screen());

    return 0;
} 

转载请注明:CodingBlog » 统计单词个数

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情