題目描述：
YXY 發(fā)現(xiàn)好多計(jì)算機(jī)中的單詞都是縮寫，如 GDB，它是全稱 Gnu DeBug 的縮寫。但是，有時(shí)縮寫對(duì)應(yīng)的全稱并不固定，如縮寫 LINUX，可以理解為：
（1）LINus's UniX （2）LINUs's miniX （3）Linux Is Not UniX
現(xiàn)在 YXY 給出一個(gè)單詞縮寫，以及一個(gè)固定的全稱（由若干個(gè)單詞組成，用空格分隔）。全稱中可能會(huì)有無效的單詞，需要忽略掉，一個(gè)合法縮寫要求每個(gè)有效的單詞中至少有一個(gè)
字符出現(xiàn)在縮寫中，縮寫必須按順序出現(xiàn)在全稱中。對(duì)于給定的縮寫和一個(gè)固定的全稱，問有多少種解釋方法。解釋方法為縮寫的每個(gè)字母出現(xiàn)在全稱中每個(gè)有效單詞中的位置，有一個(gè)字母位置不同，就認(rèn)為是不同的解釋方法。

輸入格式：
第一行輸入一個(gè) N，表示有 N 個(gè)無效單詞；接下來 N 行分別描述一個(gè)由小寫字母組成的無效單詞；接下來是若干個(gè)詢問，先給出縮寫（只有大寫字母），然后給出一個(gè)全稱。讀
入以“LAST CASE”結(jié)束。

輸出格式：
對(duì)于每個(gè)詢問先輸出縮寫，如果當(dāng)前縮寫不合法。則輸出“is not a valid abbreviation”，否則輸出“can be formed in i ways”（i 表示解釋方法種數(shù)）。

樣例輸入 ：

2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE

?

樣例輸出：

ACM can be formed in 2 ways
RADAR is not a valid abbreviation

數(shù)據(jù)范圍 ： 1<=N<=100，每行字符串長度不超過 150，詢問不超過 20，所給數(shù)據(jù)計(jì)算出
來的最后方案數(shù)不超過 10^9。

?

數(shù)據(jù)范圍很小，此題暴力修改+一般DP

貼代碼：

1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 typedef long long LL; 8 inline int read() 9 { 10 int x=0,f=1;char c=getchar(); 11 while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} 12 while(isdigit(c)){x=x*10+c-'0';c=getchar();} 13 return x*f; 14 } 15 int n,l1,l2,l3; 16 char s[160],sc[110][160],mb[160],t[160]; 17 bool judge(char *a,char *b) 18 { 19 int x=strlen(a),y=strlen(b); 20 if(x!=y)return 1; 21 for(int i=0;i<x;i++) 22 if(a[i]!=b[i])return 1; 23 return 0; 24 } 25 int main() 26 { 27 freopen("abbr.in","r",stdin); 28 freopen("abbr.out","w",stdout); 29 n=read(); 30 for(int i=0;i<n;i++)scanf("%s",sc[i]); 31 cin.getline(s,160); 32 while(1) 33 { 34 char tmp[160]; 35 memset(tmp,0,sizeof(tmp)); 36 memset(mb,0,sizeof(mb)); 37 memset(s,0,sizeof(s)); 38 cin.getline(tmp,151); 39 if(!strcmp(tmp,"LAST CASE"))break; 40 int l0=strlen(tmp);;bool ok=0; 41 l1=l2=l3=0; 42 int i = 0; 43 while(tmp[i] != ' ') mb[l1++] = tmp[i++]; 44 for(i++; i < l0; i++) s[l2++] = tmp[i]; 45 // printf("%s\n%s\n", mb, s); 46 ok=1; 47 int st=0,en=0,now=0; 48 bool had[151]; 49 memset(had,0,sizeof(had)); 50 memset(tmp,0,sizeof(tmp)); 51 memset(t, 0, sizeof(t)); 52 for(i = 0; i < l2;) { 53 char tw[160]; int tcnt = 0; 54 while(i < l2 && s[i] != ' ') { 55 tw[tcnt++] = s[i]; 56 i++; 57 } 58 i++; 59 tw[tcnt] = 0; 60 bool ok = 1; 61 for(int j = 0; j < n; j++) if(!strcmp(sc[j], tw)) { 62 ok = 0; break; 63 } 64 if(!ok) continue; 65 for(int j = 0; j < tcnt; j++) t[l3++] = tw[j]; 66 t[l3++] = ' '; 67 } 68 l3--; 69 // printf("%s %s\n", mb, t); 70 int cnt=1; 71 for(int i=0;i<l3;i++) if(t[i]==' ')cnt++; 72 if(cnt>l1) 73 { 74 printf("%s is not a valid abbreviation\n",mb); 75 continue; 76 } 77 int dp[160][160][2]; 78 memset(dp,0,sizeof(dp)); 79 for(int i=l1;i>=1;i--)mb[i]=mb[i-1]; 80 for(int i=l3;i>=1;i--)t[i]=t[i-1]; 81 // printf("new: %s %s\n", mb + 1, t + 1); 82 dp[0][0][0]=1; 83 for(int i=0;i<=l3;i++) 84 { 85 if(t[i]==' ')continue; 86 for(int j=0;j<=min(i,l1);j++) 87 { 88 // printf("%d %d: %d %d\n", i, j, dp[i][j][0], dp[i][j][1]); 89 if(t[i+1]==' ') 90 { 91 if(t[i+2]-'a'==mb[j+1]-'A')dp[i+2][j+1][1]+=dp[i][j][1]; 92 dp[i+2][j][0]+=dp[i][j][1]; 93 continue; 94 } 95 if(t[i+1]-'a'==mb[j+1]-'A')dp[i+1][j+1][1]+=(dp[i][j][0]+dp[i][j][1]); 96 dp[i+1][j][0]+=dp[i][j][0];dp[i+1][j][1]+=dp[i][j][1]; 97 } 98 } 99 for(int i=1;i<=l1;i++)printf("%c",mb[i]); 100 if(!dp[l3][l1][1])printf(" is not a valid abbreviation\n"); 101 else printf(" can be formed in %d ways\n",dp[l3][l1][1]); 102 103 } 104 return 0; 105 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/FYH-SSGSS/p/6049062.html

總結(jié)

以上是生活随笔為你收集整理的单词缩写（abbr.cpp）每日一题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。