全国赛noi湖南省选2002day

1、DNA 分子的最佳比对问题描述DNA 分子是人类遗传信息的载体，它间接地指导蛋白质的。DNA 分子是由四种核苷酸组成的长链，这四种核苷酸分别是腺嘌呤核苷酸（用 A 代表）、鸟嘌呤核苷酸（用 G 代表）、胞嘧啶核苷酸（用 C 代表）和胸腺嘧啶核苷酸（用 T 代表）。上用一个字符集为A，T，C，G的字符串来表示一个 DNA 分子序列，如 CGTTAGA。在生物进化过程中，DNA 分子可能发生各种各样的突变。这种突变形成了生物遗传信息的改变，从而使生物得以分化，了生物的多样性。主要的突变有三种：（1）在一个 DNA 序列中 一个新的核苷酸，（2）DNA 序列中丢失了一个核苷酸，（3）DNA 序列中的

2、某个核苷酸被另一个核苷酸所取代。所谓两个 DNA 序列的一个比对是寻找一种排列方式，使得两个 DNA 序列在同样的位置上有相同的核苷酸，而若在同样的位置上两个 DNA 序列的核苷酸不同，则是由三种突变之一得到。例如，对两个 DNA 序列 T =ATCAG，T第 1 行为 DNA 序列 T结点的边的时延，当其值=-1 时表示第 k 个结点到第 l 个结点无边。显然该邻接矩阵是对称矩阵。第 n+2 行到第 2n+1 行是丢失率 p 的邻接矩阵，其元素 pkl 的值是第 k 个结点到第 l 个结点的边的丢失率，已精确到小数点后 4 位，当其值=-1 时表示第 k 个结点到第 l个结点无边。显然该邻接

3、矩阵是对称矩阵。输出数据输出文件 ROUTING.OUT共 1 行，输出所找出的路径的时延和丢失率（精确到小数点后 4 位）。样例ROUTING.INROUTING.OUT 5 0.050030150110235200.1 0.050 0.050.05 0.05 0奶牛的运算问题描述最近，Farmer John 农场里的奶牛正在学习数学基础课。这天，奶牛 Besty 学会了加减法运算和括号的使用。Farmer John 为了Besty 的学习情况，写了如下一个算式：S = A1 A2 A3 A4 A5 An接着，Farmer John 告诉 Besty，这个算式中省略了 K 个括号。将这 K

4、个括号加入该算式中，就会得到一种算式方案。例如：S = A1 A2 A3 A4，K = 2，则 S = (A1) A2 (A3 A4) 就是一种算式方案。而对任意两个算式方案，S和 S本质不同是指：存在某数列 A1，A2An 满足S S。否则就是本质相同。例如：S = (A1) A2 (A3 A4) 与 S = (A1 A2) (A3 A4)就是本质相同的算式方案。现在，Farmer John 告诉奶牛 Besty 算式中项的个数 N 和括号的个数 K（数列 A 是变量，不需要关心它），他想考考 Besty 究竟有多少本质不同的算式方案。输入文件输入文件名：count.in输入文件仅一行，依次

5、为两个整数 N 和 K。（1 N , K 100）输出文件输出文件名：count.out输出文件仅一行，为本质不同的算式方案数。样例输入4 1样例输出4节问题描述明天就是 2 月 14 日的了。本来是一件令人高兴地事，但 John 却为明天的节而非常烦恼。John 走遍了各个商店，但没有一件正当他将要失去信心时，电视中的一个能使他满意的，他觉得那些都缺乏新意。引起了他的注意。“这里是 XX，明，。我天就是节了，的周末将在明出节特别鲜花献给有请各位观众赶快拨打的，前 30 对拨打的观众将会有机会在现场参们的们这次的内容有”其中有一个是：将从天上撒下许多鲜花，而参加节目的观众可以推着一个小车，来回

6、移动以接住这些鲜花，最后将根据你所得到的鲜花决定获得的，而你所获得的鲜花也可以全部归自己所有，送给自己心爱的人。奖品倒是无所谓，John 知道他的女朋友是很喜欢鲜花的，特别是有这么多各式各样的品种。John 于是马上拨打了的号码。竟然刚好是第 30 位，他太幸运了。为了珍惜这次难得的机会，John 发誓他一定要获得大奖。通过对这个过程的分析，John 发现的场地可以划分成 1*N 个方格，一开始你将站在第N div 2 个方格内。每个时刻都可能有鲜花落下，而一旦鲜花，你将不能把它捡起来放进小车内。由于小车有一定的重量，控制时并不是特别容易，你在每一时间能让小车的速度加 1，减 1 或者不变。假设你当前的位置是 5，速度是 7，下一时间内只你的位置将只能是 11,12 或者 13，对应的速度将分别是 6,7,8。与此同时，每朵鲜花也有着不同的分值。获得最高的分值总和就是最终的目的。输入输出文件输入文件为 flower.in，文件的第一行有三个整数 N,M,V(N=100,M=1000000,1=V=5),分别表示场地的宽的度和掉落鲜花数和移动速度。接下来M 行，每行有三个整数 i,j,k，按照鲜花时间，位置和分值。时间的先后顺序，给出了鲜花的输出文件为 flower.out，第一行为你的程序得到的最大分值总和，接下来每行