題意：給出兩個串a，b，去構建另一個串，新構建出來的串要滿足兩個性質。一，在這個新的串中選出一個子集是a串，另外選出一個子串是b，滿足這個條件后，要求這個串的長度最短。也可以這樣說，ab兩個串合并為一個新串，不改變a，b串本身的相對位置，但是要求新串長度最短。輸出這樣的新串的個數

所以基本上可以想到，是和LCS有關的，再細想，那就是算出LCS的長度，然后ab兩串長度之和減去LCS的長度，相當于ab兩串合并為一串，消去他們的共有元素，那么新串中還是包含了a，b串的所有元素還是可以選出一部分子集來得到a或b串的。

但問題時，怎么構建，另外有多少種構建方法，實際上構建的方案數就是最后新串的個數

我們可以模仿LCS的構建方法來思考這個問題 ? ?c[i][j]表示a串前i個元素和b串前j個元素所能得到的方案數。l[i][j]表示LCS的長度

若a[i]=b[j]，那么c[i][j]=c[i-1][j-1],即a串前i-1個元素和b串前j-1個元素得到的組合串的末尾加上一個相同的元素a[i]，那么得到的新的組合串的個數還是和之前的組合串的個數一樣

若a[i]!=b[j], ?l[i][j]=max { l[i-1][j] , l[i][j-1]}

若l[i-1][j]>l[i][j-1],那說明從l[i-1][j]這種狀態開始構建才能得到最終的LCS同時最終的組合串才不能漏掉共有的元素，所以c[i][i]=c[i-1][j],即在a串i-1個元素和b串j個元素組成的組合串的后面加上a[i]，那么得到的新的組合串的個數和之前的組合串的個數是相同的

若l[i][j-1]>l[i-1][j],道理和上面是一樣的，所以c[i][j]=c[i][j-1],相當于在之前的組合串后面加上元素b[j],得到新的組合串的個數不變

若l[i][j-1]=l[i-1][j],說明從兩種狀態都是能得到最終的LCS并且最終的組合串不會漏掉任何相同的公共元素，所以c[i][j]=c[i-1][j]+c[i][j-1] , 即用a串的i-1個元素和b串的j個元素組成的組合串的最后加上a[i]得到新的組合串和之前的組合串個數相同，另外用a串的i個元素和b串的的j-1個元素組成的組合串的最后加上b[j]得到新的組合串和之前的組合串個數相同，那么就是兩者之和

?

另外讀取a，b串的時候要用gets，就這樣WA了兩次

另外c[][]數組同long long?

?

#include <stdio.h> #include <string.h> #define MAX 40 char a[MAX],b[MAX]; int l[MAX][MAX]; long long c[MAX][MAX]; int lena ,lenb;int main() {int T,t,i,j;scanf("%d",&T); getchar();for(t=1; t<=T; t++){gets(a+1);gets(b+1);//scanf("%s%s",a+1,b+1);lena=strlen(a+1);lenb=strlen(b+1);memset(l,0,sizeof(l));memset(c,0,sizeof(c));for(i=0; i<=lena; i++)c[i][0]=1;for(i=0; i<=lenb; i++)c[0][i]=1;for(i=1; i<=lena; i++)for(j=1; j<=lenb; j++){if(a[i]==b[j]){l[i][j]=l[i-1][j-1]+1;c[i][j]=c[i-1][j-1];}else{if(l[i-1][j]>l[i][j-1]){l[i][j]=l[i-1][j];c[i][j]=c[i-1][j];}else if(l[i][j-1]>l[i-1][j]){l[i][j]=l[i][j-1];c[i][j]=c[i][j-1];}else{l[i][j]=l[i-1][j];c[i][j]=c[i-1][j]+c[i][j-1];}}}printf("Case #%d: %d %lld\n",t,lena+lenb-l[lena][lenb] , c[lena][lenb]);}return 0; }

轉載于:https://www.cnblogs.com/scau20110726/archive/2012/10/01/2709781.html

總結

以上是生活随笔為你收集整理的uva 10723 Cyborg Genes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。