P1624 单词缩写

题目描述

树树发现好多计算机中的单词都是缩写，如GDB是全称Gnu DeBug的缩写。但是，有时候缩写对应的全称会不固定，如缩写LINUX可以理解为：

（1） LINus’s UniX

（2） LINUs’s miniX

（3） Linux Is Not UniX

现在树树给出一个单词缩写，以及一个固定的全称（若干个单词组成，空格隔开）。全

称中可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中，所写必须按顺序出现在全称中。

对于给定的缩写和一个固定的全称，问有多少种解释方法？解释方法为所写的每个字母在全称每个有效单词中出现的位置，有一个字母位置不同，就认为是不同的解释方法。

输入输出格式

输入格式：

 

第一行输入一个N，表示有N个无效单词；

接下来N行分别描述一个由小写字母组成的无效单词；

最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以“LAST CASE”结束。

[数据规模]

1≤N≤100，每行字符串长度不超过150，询问次数不超过20，最后方案数不超过10^9。

 

输出格式：

 

对于每个询问先输出缩写，如果当前缩写不合法，则输出“is not a valid abbreviation”,否则输出“can be formaed in i ways”(i表示解释方法数)

 

输入输出样例

输入样例#1： 

2andofACM academy of computer makersRADAR radio detection and rangingLAST CASE

输出样例#1： 

ACM can be formed in 2 waysRADAR is not a valid abbreviation

 

洛谷题解

先暴力去掉所有的单词，只对有效单词进行计算。

dp[i][j]表示前i个单词使用了前j个大写字母的方案数

初始条件dp[0][0]=1

转移：若第i个单词使用第j到第j+k个大写字母的方案数为temp[k]

则dp[i][j+k]=dp[i-1][j-1]*temp[k]

最终ans=dp[n][m]

时间复杂度Ｏ（Ｌ１＊Ｎ＊Ｌ２＊Ｌ２）

空间复杂度Ｏ(Ｌ１*Ｎ*Ｌ２)

L1缩写长度 N全称中单词的个数 L2全称中一个单词的长度

 

这属于两个串匹配的问题，就一个前i，一个前j就好，反正是找子问题。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 char w[101][150]; 7 char s[150],let[150]; 8 char over[9]={
   'L','A','S','T',' ','C','A','S','E'}; 9 struct word10 {11     char c[150];12     int l;13 }a[150];14 int t,n,m,len;15 int dp[100][150],temp[150];16 bool Case_is_Over()17 {18     for (int i=0;i<=8;i++)19         if (s[i]!=over[i]) return false;20     return true;21 }22 int main()23 {24     freopen("abbr.in","r",stdin);25     freopen("abbr.out","w",stdout);26     scanf("%d\n",&t);27     for (int i=1;i<=t;i++) scanf("%s",w[i]);28     while (233)29     {30         char ch=getchar();len=0;31         while ( ! ( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') || ch==' ' ) ) ch=getchar();32         while ( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') || ch==' ' ) s[len++]=ch,ch=getchar();33         n=m=0;//设每个询问有n个单词，m个大写字母34         if (Case_is_Over()) break;35         int p=0;36         for (int i=1;i<150;i++) memset(a[i].c,0,sizeof(a[i].c)),a[i].l=0;37         while (s[p]>='A'&&s[p]<='Z')38         {39             printf("%c",s[p]);40             let[++m]=s[p]+32;41             p++;42         }43         p++;44         while (p
         
          ='a'&&s[p]<='z')48             {49                 a[n].c[a[n].l++]=s[p];50                 p++;51             }52             for (int i=1;i<=t;i++)53                 if (strcmp(w[i],a[n].c)==0)54                 {55                     memset(a[n].c,0,sizeof(a[n].c));56                     a[n].l=0;57                     n--;break;58                 }59             p++;60         }61         memset(dp,0,sizeof(dp));62         dp[0][0]=1;63         for (int i=1;i<=n;i++) //枚举单词64             for (int j=i;j<=i+m-n;j++) //枚举当前单词使用大写字母的起始位置65             {66                 memset(temp,0,sizeof(temp));67                 for (int p=0;p
          
           =0;k--) //恰好等于第j+k个大写字母69 if (let[j+k]==a[i].c[p])70 if (k) temp[k]+=temp[k-1];71 else temp[k]++;72 for (int k=i+m-n-j;k>=0;k--)73 dp[i][j+k]+=dp[i-1][j-1]*temp[k];74 }75 if (dp[n][m]) printf(" can be formed in %d ways\n",dp[n][m]);76 else printf(" is not a valid abbreviation\n");77 }78 return 0;79 }
          
         
        
       
      
     

 

 

 

 

 

 

 

 

 

看大家都是N^4或N³算法，N²算法还没有，赶紧水一发

基本思路:

把所有串连接起来，记录每个串的尾后位置，

设f[k][i]表示现在在处理缩写的第K个字符，在大字符串中第I个位置对前面字符的总贡献数，则f[k][i]=Σf[k-1][j]，

其中j表示满足条件的前一个缩写字符。其中满足条件的定义为“无空缺单词，且是前一个字母”。则答案为Σf[最后一个字符][j],(1<=j<=n)。

为避免出现同一字母出现位置的不同，用一个数组进行标记即可。

标记要一次打完才能更新！！！

 

1 #include
     
        2 #define RG register  3 using namespace std;  4   5 int n;  6 char a[110][200];//无效单词  7 char c1[200];  8 char c[200];  9 char all[200][200];//有效单词 10 int ma[26][200];//每个字母的有效位置 11 int tag[200]; 12 int tag1[200];//两个标记 13 int cut[200];//单词的尾后位置 14 int sum[26];//出现的次数 15 int f[200][200];//dp数组 16  17 int main() 18 { 19     scanf("%d\n",&n); 20     for(RG int i=1;i<=n;i++) 21     { 22         scanf("%s",a[i]); 23     } 24     scanf("%s",c1); 25     while(1) 26     { 27         RG int i_1_1=1; 28         strcpy(c,c1); 29         if(strcmp(c,"LAST")==0) 30         { 31             scanf("%s",all[i_1_1++]); 32             if(strcmp(all[i_1_1-1],"CASE")==0) break; 33         } 34         while(cin>>all[i_1_1++]) 35         { 36             RG int j=0; 37             int len=strlen(all[i_1_1-1]); 38             while(all[i_1_1-1][j]<'a'&&j
      
       =len) 40             { 41                 strcpy(c1,all[i_1_1-1]); 42                 i_1_1--; 43                 break; 44             } 45             else 46             { 47                 for(RG int i=1;i<=n;i++) 48                 { 49                     if(strcmp(a[i],all[i_1_1-1])==0) 50                     { 51                         i_1_1--; 52                         break; 53                     } 54                 } 55             } 56         } 57         i_1_1--; 58         printf("%s ",c); 59         int len=strlen(c); 60         for(RG int i=0;i
       
        =cut[ti]) ti++;123                     if(i_1_1-ti>len-k-1) continue;124                     if(k==0)125                     {126                         tag1[ma[id][i]]=0;//标记127                         f[k][i]=1;//初始值128                     }129                     else130                     {131                         int t=c[k-1]-'a';132                         for(int j=1;j<=sum[t];j++)133                         {134                             if(ma[t][j]
        
         =cut[ti-2]&&tag[ma[t][j]]==k-1)135                             {136                                 f[k][i]+=f[k-1][j];//转移137                                 tag1[ma[id][i]]=k;//标记×2138                             }139                         }140                     }141                 }142                 for(int i=0;i