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}

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。

猜你喜欢