|
題目描述： 基因串是由一串有限長度的基因所組成的，其中每一個(gè)基因都可以用26個(gè)英文大寫字母中的一個(gè)來表示，不同的字母表示不同的基因類型。一個(gè)單獨(dú)的基因可以生長成為一對新的基因，而可能成長的規(guī)則是通過一個(gè)有限的成長規(guī)則集所決定的。每一個(gè)成長的規(guī)則可以用三個(gè)大寫英文字母A1A2A3來描述，這個(gè)規(guī)則的意思是基因A1可以成長為一對基因A2A3。
用大寫字母S來表示一類稱作超級基因的基因，因?yàn)槊恳粋€(gè)基因串都是由一串超級基因根據(jù)給出的規(guī)則所成長出來的。 請寫一個(gè)程序，讀入有限條成長的規(guī)則和一些我們想要得到的基因串，然后對于每個(gè)基因串，判斷它是否可以由一個(gè)有限長度的超級基因串成長得出。如果可以，給出可成長為該基因串的最短超級基因串的長度。 關(guān)于輸入 第一行為正整數(shù)n(n<=50)表示規(guī)則的數(shù)目。 接下來n行，每行一個(gè)規(guī)則。 最后一行是目標(biāo)基因串，長度不超過100。 關(guān)于輸出
輸出最短的超級基因串的長度，如果無法生成，請輸出-1 例子輸入 3 BCA ABC SAB BCCA
例子輸出 1 乍看題目，好像無從下手，好在題目給了詳盡的提示解法。 S->AB->BCB->BCCA 此題和石子歸并問題類似,可以用f[i][j][C]表示從i到j(luò)的子串能否由C推導(dǎo)得出,f[i][j][C]=0表示不能,f[i][j][C]=1表示能,則有: f[i][j][C]=max{f[i][k][A]*f[k+1][j][B]}其中i<=k 這樣可以計(jì)算出每一段能否由一個(gè)超級基因S推導(dǎo)得出. 再由一次類似的動態(tài)規(guī)劃過程可以算出每個(gè)子串最少由幾個(gè)S推導(dǎo)得出(比如用g[i][j]表示從i到j(luò)的子串至少由幾個(gè)S推導(dǎo)得出),即得到原問題的解. 構(gòu)建一個(gè)100*100*26（26為字母的數(shù)量）大小的bool型數(shù)組并不算大，用不了1M的空間即可。 而且，在程序運(yùn)行中，大多數(shù)的空間是用不到的，因?yàn)閮H有少數(shù)的字母可以用到。 代碼： // Author : Marchon #include<iostream> using namespace std; bool f[100][100][26]; int Trans[50][3]; char Target[111]; int L,n; void func() { for(int i = 0; i < L; i++) { f[i][0][Target[i]-'A'] = true; } for(int j = 1; j < L; j++) { for(int i = 0; i < L-j; i++) { for(int t = 0; t < n; t++) { int max = 0; for(int k = 0; k < j; k++) { max += f[i][k][Trans[t][1]] * f[i+k+1][j-k-1][Trans[t][2]]; } f[i][j][Trans[t][0]] += max; } } } } int findS(int begin) { if(f[begin][L-begin-1][18]) return 1; int result = 9999; for(int i = L-1; i >= begin; i--) { if(f[begin][i-begin][18]) { int temp = 1 + findS(i+1); if(temp < result) result = temp; } } return result; } int main() { cin >> n; for(int i = 0; i < n; i++) { char s,a,b; cin >> s >> a >> b; Trans[i][0] = s - 'A'; Trans[i][1] = a - 'A'; Trans[i][2] = b - 'A'; } cin >> Target; L = strlen(Target); memset(f,0,sizeof(f)); func(); int min = findS(0); if(min >= 9999) cout << "-1" << endl; else cout << min << endl; return 0; } Case 0: Time = 6ms, Memory = 272kB. Case 1: Time = 12ms, Memory = 272kB. Case 2: Time = 6ms, Memory = 272kB. Case 3: Time = 6ms, Memory = 272kB. Case 4: Time = 30ms, Memory = 272kB. Case 5: Time = 18ms, Memory = 272kB. Case 6: Time = 64ms, Memory = 272kB. Case 7: Time = 73ms, Memory = 272kB. Case 8: Time = 138ms, Memory = 392kB. Case 9: Time = 141ms, Memory = 392kB. |
|
|
