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}
本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。