<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0045)http://acm.pku.cn/JudgeOnline/problem?id=2414 -->
<HTML><HEAD><TITLE>2414 -- Phylogenetic Trees Inherited</TITLE>
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<STYLE type=text/css>A {
TEXT-DECORATION: none
}
A:hover {
COLOR: red; TEXT-DECORATION: underline
}
</STYLE>
<META content="MSHTML 6.00.2900.2912" name=GENERATOR></HEAD>
<BODY vLink=blue aLink=blue link=blue bgColor=#f1f1fd leftMargin=5><A
name=top></A>
<TABLE style="BORDER-COLLAPSE: collapse" borderColor=#ffffff width=980
border=1><TBODY>
<TR>
<TD align=middle colSpan=5><IMG height=97
src="2414 -- Phylogenetic Trees Inherited.files/logo.jpg" width=980
border=0></TD></TR>
<TR vAlign=top align=middle bgColor=#6589d1>
<TH width=196>Online Judge</TH>
<TH width=196>Problem Set</TH>
<TH width=196>Authors</TH>
<TH width=197>Online Contests</TH>
<TH width=197>User</TH></TR>
<TR vAlign=top align=middle bgColor=#f1f1fd>
<TD><A href="http://acm.pku.cn/JudgeOnline/bbs">Web Board</A><BR><A
href="http://acm.pku.cn/JudgeOnline/">Home Page</A><BR><A
href="http://acm.pku.cn/JudgeOnline/faq.htm"
target=_blank>F.A.Qs</A><BR>Announcement</TD>
<TD>
<FORM action=gotoproblem method=get><A
href="http://acm.pku.cn/JudgeOnline/problemlist">Problems</A><BR><A
href="http://acm.pku.cn/JudgeOnline/submit">Submit Problem</A><BR><A
href="http://acm.pku.cn/JudgeOnline/status">Status (Online)</A><BR><FONT
color=blue>Prob.ID:</FONT><INPUT size=6 name=pid><INPUT type=submit value=Go name=pb1></FORM></TD>
<TD>
<FORM action=searchuser method=get><A
href="http://acm.pku.cn/JudgeOnline/register">Register</A><BR><A
href="http://acm.pku.cn/JudgeOnline/modifyuser">Update your info</A><BR><A
href="http://acm.pku.cn/JudgeOnline/userlist">Authors
ranklist</A><BR><INPUT size=10 name=key><INPUT type=submit value=Search name=B1></FORM></TD>
<TD><FONT color=#1a5cc8>Current Contest</FONT><BR><A
href="http://acm.pku.cn/JudgeOnline/pastcontests">Past Contests</A><BR><A
href="http://acm.pku.cn/JudgeOnline/contests"><FONT color=red>Scheduled
Contests</FONT></A><BR><A
href="http://acm.pku.cn/JudgeOnline/awardcontest_announce.htm"
target=_blank><FONT color=red>Award Contest</FONT></A></TD>
<TD align=left>
<FORM action=login method=post>User ID: <INPUT size=10
name=user_id1><BR>Password:<INPUT type=password size=10
name=password1><BR><INPUT type=submit value=login name=B1> <A
href="http://acm.pku.cn/JudgeOnline/register"
target=_parent>Register</A><INPUT type=hidden
value=/JudgeOnline/problem?id=2414 name=url></FORM></TD></TR></TBODY></TABLE>
<TABLE width="100%"
background="2414 -- Phylogenetic Trees Inherited.files/table_back.jpg"
border=0><TBODY>
<TR>
<TD>
<P align=center><FONT color=blue size=5>Phylogenetic Trees
Inherited</FONT> <BR>Time Limit:3000MS Memory Limit:65536K<BR>Total
Submit:95 Accepted:51 <FONT color=red>Special Judged</FONT> </P>
<P><FONT color=blue size=5>Description</FONT><BR><FONT
face="Times New Roman" size=3>Among other things, Computational Molecular
Biology deals with processing genetic sequences. Considering the
evolutionary relationship of two sequences, we can say that they are
closely related if they do not differ very much. We might represent the
relationship by a tree, putting sequences from ancestors above sequences
from their descendants. Such trees are called phylogenetic trees.
<BR>Whereas one task of phylogenetics is to infer a tree from given
sequences, we'll simplify things a bit and provide a tree structure - this
will be a complete binary tree. You'll be given the n leaves of the tree.
Sure you know, n is always a power of 2. Each leaf is a sequence of amino
acids (designated by the one-character-codes you can see in the figure).
All sequences will be of equal length l. Your task is to derive the
sequence of a common ancestor with minimal costs. <BR>
<CENTER>
<TABLE>
<TBODY>
<TR>
<TD>
<TABLE border=1>
<TBODY>
<TR>
<TD>Amino Acid</TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD>Alanine</TD>
<TD>Ala</TD>
<TD>A</TD></TR>
<TR>
<TD>Arginine</TD>
<TD>Arg</TD>
<TD>R</TD></TR>
<TR>
<TD>Asparagine</TD>
<TD>Asn</TD>
<TD>N</TD></TR>
<TR>
<TD>Aspartic Acid</TD>
<TD>Asp</TD>
<TD>D</TD></TR>
<TR>
<TD>Cysteine</TD>
<TD>Cys</TD>
<TD>C</TD></TR>
<TR>
<TD>Glutamine</TD>
<TD>Gln</TD>
<TD>Q</TD></TR>
<TR>
<TD>Glutamic Acid</TD>
<TD>Glu</TD>
<TD>E</TD></TR>
<TR>
<TD>Glycine</TD>
<TD>Gly</TD>
<TD>G</TD></TR>
<TR>
<TD>Histidine</TD>
<TD>His</TD>
<TD>H</TD></TR>
<TR>
<TD>Isoleucine</TD>
<TD>Ile</TD>
<TD>I</TD></TR></TBODY></TABLE></TD>
<TD width="30%"></TD>
<TD>
<TABLE border=1>
<TBODY>
<TR>
<TD>Amino Acid</TD>
<TD></TD>
<TD></TD></TR>
<TR>
<TD>Leucine</TD>
<TD>Leu</TD>
<TD>L</TD></TR>
<TR>
<TD>Lysine</TD>
<TD>Lys</TD>
<TD>K</TD></TR>
<TR>
<TD>Methionine</TD>
<TD>Met</TD>
<TD>M</TD></TR>
<TR>
<TD>Phenylalanine</TD>
<TD>Phe</TD>
<TD>F</TD></TR>
<TR>
<TD>Proline</TD>
<TD>Pro</TD>
<TD>P</TD></TR>
<TR>
<TD>Serine</TD>
<TD>Ser</TD>
<TD>S</TD></TR>
<TR>
<TD>Threonine</TD>
<TD>Thr</TD>
<TD>T</TD></TR>
<TR>
<TD>Tryptophan</TD>
<TD>Trp</TD>
<TD>W</TD></TR>
<TR>
<TD>Tyrosine</TD>
<TD>Tyr</TD>
<TD>Y</TD></TR>
<TR>
<TD>Valine</TD>
<TD>Val</TD>
<TD>V</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></CENTER><BR>The
costs are determined as follows: every inner node of the tree is marked
with a sequence of length l, the cost of an edge of the tree is the number
of positions at which the two sequences at the ends of the edge differ,
the total cost is the sum of the costs at all edges. The sequence of a
common ancestor of all sequences is then found at the root of the tree. An
optimal common ancestor is a common ancestor with minimal total costs.
</FONT>
<P></P>
<P><FONT color=blue size=5>Input</FONT><BR><FONT face="Times New Roman"
size=3>The input file contains several test cases. Each test case starts
with two integers n and l, de
PKU动态规划题集v1.0Beta1 （316个子文件） 
style.css 2KB
bugs.gif 7KB 2414.htm 10KB 1157.htm 10KB 2439.htm 10KB 2355.htm 9KB 1093.htm 9KB 1685.htm 8KB 1015.htm 8KB 2397.htm 8KB 1170.htm 7KB 1631.htm 7KB 1038.htm 7KB 1923.htm 7KB 1925.htm 7KB 1156.htm 7KB 1722.htm 7KB 2385.htm 7KB 2430.htm 7KB 1953.htm 7KB 2250.htm 7KB 1036.htm 7KB 1221.htm 7KB 1732.htm 7KB 2133.htm 7KB 2151.htm 7KB 2393.htm 7KB 1821.htm 7KB 2033.htm 7KB 1014.htm 7KB 1018.htm 7KB 1678.htm 6KB 1160.htm 6KB 1909.htm 6KB 2441.htm 6KB 2342.htm 6KB 1745.htm 6KB 2181.htm 6KB 1651.htm 6KB 1661.htm 6KB 1050.htm 6KB 1579.htm 6KB 2247.htm 6KB 1458.htm 6KB 1159.htm 6KB 1191.htm 6KB 1163.htm 6KB 2442.htm 6KB 1088.htm 6KB 2229.htm 6KB 1338.htm 5KB 1664.htm 5KB Catalog.htm 5KB
1631_1.jpg 36KB 1925_1.jpg 26KB 1923_1.jpg 26KB 2439_2.jpg 19KB 1191_1.jpg 17KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB logo.jpg 15KB共 316 条
- 1
- 2
- 3
- 4
评论7
最新资源