noip2001 統計單詞個數 （動态規劃-劃分）

P1118統計單詞個數

​​Accepted​​

标簽：

​​動态規劃​​​

​​​NOIP提高組2001​​

描述

給出一個長度不超過200的由小寫英文字母組成的字母串(約定;該字串以每行20個字母的方式輸入，且保證每行一定為20個)。要求将此字母串分成k份(1<k<=40)，且每份中包含的單詞個數加起來總數最大(每份中包含的單詞可以部分重疊。當選用一個單詞之後，其第一個字母不能再用。例如字元串this中可包含this和is，選用this之後就不能包含th)。

單詞在給出的一個不超過6個單詞的字典中。

要求輸出最大的個數。

格式

輸入格式

第一行有二個正整數(p，k)

p表示字串的行數;

k表示分為k個部分。

接下來的p行，每行均有20個字元。

再接下來有一個正整數s，表示字典中單詞個數。(1<=s<=6)

接下來的s行，每行均有一個單詞。

輸出格式

輸出一個整數，即最大的個數

樣例1

樣例輸入1[複制]

1 3

thisisabookyouareaoh

4

is

a

ok

sab

樣例輸出1[複制]

7

限制

每個測試點1s

來源

NOIP2001第三題

解析：s[i][j]表示從 i 到 j 有多少個單詞，f[i][j] 表示将 [0，i] 分成 j 個部分時的最大單詞數，則有

          f[i][j]=max{ f[k][j-1]+s[k+1][i] }

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=200;
int n,m,length=0,len[10];
int f[maxn+20][50];
int s[maxn+20][maxn+20];
char a[maxn+20],b[10][maxn+20];

void readdata()
{
  int i,j,k;
  scanf("%d%d",&k,&n);
  for(i=1;i<=k;i++)
    {
      scanf("%s",b[0]);
      for(j=0;j<20;j++)a[length++]=b[0][j];
  }
  scanf("%d",&m);
  for(i=1;i<=m;i++)
    {
      scanf("%s",b[i]);
      len[i]=strlen(b[i]);
  }
}

int pipei(int l,int r)
{
  int i,j;
  for(i=1;i<=m;i++)
    {
      if(len[i]>r-l+1)continue;
      for(j=0;j<len[i];j++)
        if(a[l+j]!=b[i][j])break;
      if(j>=len[i])return 1;
  }
  return 0;
}

void work()
{
  int i,j,k;
  for(i=0;i<length;i++)
    for(j=i;j<length;j++)
      for(k=i;k<=j;k++)
        s[i][j]+=pipei(k,j);
  
  for(i=0;i<length;i++)f[i][1]=s[0][i];
  for(k=2;k<=n;k++)
    for(i=k-1;i<length;i++)
      for(j=k-2;j<i;j++)
        f[i][k]=max(f[i][k],f[j][k-1]+s[j+1][i]);
  printf("%d\n",f[length-1][n]);
}

int main()
{
  readdata();
  work();
  return 0;
}