POI 9706 Genotype 解題報告 | 宁心勉学，慎思笃行

Genotype 是一個有限的基因序列。它是由大寫的英文字母A-Z組成，不同的字母表示不同種類的基因。

一個基因可以分化成為一對新的基因。這種分化被一個定義的規則集合所控制。每個分化的規則可以用三個大寫字母A1A2A3表示，含義為基因A1可以分化成A2A3。

我們用S代表特種基因，繁殖genotype是從特種基因序列開始。

根據給定的規則，它由被選擇控制規則對基因不斷進行繁殖而成。

任務

從文本文件GEN.IN 讀入一個定義的規則集和一個想生成的genotypes 單詞序列。對每一個給定的 genotype，根據給定的分化規則，檢查是否它能從某一個確定特種基因序列生成，如果能，找到最小的序列長度，將結果寫入文本文件GEN.OUT。輸入在文件GEN.IN 的第一行有一個整數n, 1 <= n <= 10000. 下面n 每一行為一個分化規則. 這些規則都由包含A – Z的三個大寫字母組成. 接下來有一個整數k, 1 <= k <= 10000. 接下來的k 行有一個 genotype. Genotype由沒有空格的單詞組成，最多100 個英文大寫字母. 輸出在文件GEN.OUT中有k行,在第I行應寫入: 一個正整數――需要生成第I個genotypes的最小長度；或者單詞 NIE, 如果不能生成對應的genotype。

GEN.IN: 6 SAB SBC SAA ACA BCC CBC 3 ABBCAAABCA CCC BA

GEN.OUT: 3 1 NIE

這道題是典型的雙重動態規劃。

第一步：由題意可以知道，分化具有階段性和規律性，這正是動態規劃的特徵。由於要求的是最少的特等基因數目，所以考慮一次分化的情況。要一次分化到的串設為T，假設字符Ch1能夠一次分化成Ch2和Ch3，並且Ch2能夠一次分化成從第p位到第i位的字符串，而Ch3能夠一次分化成從第i+1位到第q位的字符串，那麼必有Ch1能夠一次分化到從第p位到第q位的字符串。如Ch1=S,Ch2=A,Ch3=B時，S->AB，A->BC，B-> CD，則 S -> BCCD。需要窮舉 Ch2 和 Ch3，所以使用了數組模擬鏈表。動態轉移方程如下：

 can[ch1,p,q]:= can[ch2,p,i] and can[ch3,i+1,j]

其中ch1能夠一次分化到ch2和ch3。這裡的i作為劃分點，再次體現了二分的思想。

由於本人的程序中使用了記憶化搜索的思想，所以 can 設置為了數值型，初始值為 0，能夠一次分化為 1，否則為 2。

第二步：由上面的思路可以得出任意一個字符Ch能否一步分化到字串T的任意一段。那麼，如何得出指定字串至少由S多少次分化可以得到呢？可以再次使用動態規劃思想。假設DP

\[i\]

表示T的前i位字串至少需要的特等基因的數目，那麼易得動態轉移方程如下：

 DP[i]:= min {DP[j] + 1};

其中的 j 符合

 can['S',j+1,i]=true

（或，記憶化搜索中使用

 can['S',j+1,i]=1

）

完整代碼如下：

//By Ceeji 
//From: HAOI Test 4 - Progblem 1 : Genotype 
//Date: 2009-4-4 
//Type: DP 
//States: Accepted 
Program geno; 
Type node=record 
            ch1,ch2:char; 
            next:longint; 
          end; 
Const inf='gen.in'; 
      ouf='gen.out'; 
      maxl=100; 
      maxn=10000; 
Var n,k,u,m:longint; // n : number of strings of input 
    f:array['A'..'Z']of longint; 
    hz:array[1..10000]of node; 
    can:array['A'..'Z',1..maxl,1..maxl]of integer; 
    dp:array[1..maxl]of longint; 
    str:string; 
Procedure add(ch1,ch2,ch3:char); 
begin 
   hz[m].ch1:=ch2; 
   hz[m].ch2:=ch3; 
   hz[m].next:=f[ch1]; 
   f[ch1]:=m; 
end; 
     
//Init the program 
Procedure init; 
var i:longint; 
    ch1,ch2,ch3:char; 
begin 
   assign(input,inf);   reset(input);  
   assign(output,ouf);  rewrite(output);  
   fillchar(f,sizeof(f),0);  
   fillchar(hz,sizeof(hz),0); 
   readln(n); m:=0; 
   for m:=1 to n do 
   begin 
     readln(ch1,ch2,ch3); 
     add(ch1,ch2,ch3); 
   end; 
   readln(k); 
end; 
 
//Check whether it can be creeated from the parent. The double DP. 
Function check(c:char; p,q:longint):boolean; 
var i,k:longint; 
begin 
   if can[c,p,q]<>0 then exit(can[c,p,q]=1); 
   if (c=str[p])and(p=q) then begin can[c,p,q]:=1; exit(true); end; 
   for i:=p to q-1 do 
   begin 
      k:=f[c]; 
      while k<>0 do 
      begin 
        if (check(hz[k].ch1,p,i))and(check(hz[k].ch2,i+1,q)) then 
        begin 
          can[c,p,q]:=1; exit(true);         
        end; 
        k:=hz[k].next; 
      end; 
   end; 
   can[c,p,q]:=2;  
   exit(false); 
end; 
 
//Do a simple work 
Procedure doit; 
var i,j,len:longint; 
    c:char; 
begin 
   readln(str); 
   len:=length(str); 
   fillchar(can,sizeof(can),0); 
   for i:=1 to len do  
     dp[i]:=1000000; 
   dp[0]:=0; 
   for i:=1 to len do 
   begin 
     for j:=0 to i-1 do 
     begin 
       if (dp[i]>dp[j]+1)and(check('S',j+1,i))then 
          dp[i]:=dp[j]+1; 
     end; 
   end; 
   if dp[len]>=1000000 then writeln('NIE') 
   else writeln(dp[len]); 
end; 
 
//End the output 
Procedure endPro; 
begin 
   close(output);  
end; 
{main} 
begin 
   init; 
   for u:=1 to k do 
      doit; 
   endpro;  
end.{main}

猜你喜歡