全國賽noi湖南省選2002day

1、DNA 分子的最佳比對問題描述DNA 分子是人類遺傳信息的載體，它間接地指導(dǎo)蛋白質(zhì)的。DNA 分子是由四種核苷酸組成的長鏈，這四種核苷酸分別是腺嘌呤核苷酸（用 A 代表）、鳥嘌呤核苷酸（用 G 代表）、胞嘧啶核苷酸（用 C 代表）和胸腺嘧啶核苷酸（用 T 代表）。上用一個字符集為A，T，C，G的字符串來表示一個 DNA 分子序列，如 CGTTAGA。在生物進化過程中，DNA 分子可能發(fā)生各種各樣的突變。這種突變形成了生物遺傳信息的改變，從而使生物得以分化，了生物的多樣性。主要的突變有三種：（1）在一個 DNA 序列中 一個新的核苷酸，（2）DNA 序列中丟失了一個核苷酸，（3）DNA 序列中的

2、某個核苷酸被另一個核苷酸所取代。所謂兩個 DNA 序列的一個比對是尋找一種排列方式，使得兩個 DNA 序列在同樣的位置上有相同的核苷酸，而若在同樣的位置上兩個 DNA 序列的核苷酸不同，則是由三種突變之一得到。例如，對兩個 DNA 序列 T =ATCAG，T第 1 行為 DNA 序列 T結(jié)點的邊的時延，當其值=-1 時表示第 k 個結(jié)點到第 l 個結(jié)點無邊。顯然該鄰接矩陣是對稱矩陣。第 n+2 行到第 2n+1 行是丟失率 p 的鄰接矩陣，其元素 pkl 的值是第 k 個結(jié)點到第 l 個結(jié)點的邊的丟失率，已精確到小數(shù)點后 4 位，當其值=-1 時表示第 k 個結(jié)點到第 l個結(jié)點無邊。顯然該鄰接

3、矩陣是對稱矩陣。輸出數(shù)據(jù)輸出文件 ROUTING.OUT共 1 行，輸出所找出的路徑的時延和丟失率（精確到小數(shù)點后 4 位）。樣例ROUTING.INROUTING.OUT 5 0.050030150110235200.1 0.050 0.050.05 0.05 0奶牛的運算問題描述最近，F(xiàn)armer John 農(nóng)場里的奶牛正在學(xué)習(xí)數(shù)學(xué)基礎(chǔ)課。這天，奶牛 Besty 學(xué)會了加減法運算和括號的使用。Farmer John 為了Besty 的學(xué)習(xí)情況，寫了如下一個算式：S = A1 A2 A3 A4 A5 An接著，F(xiàn)armer John 告訴 Besty，這個算式中省略了 K 個括號。將這 K

4、個括號加入該算式中，就會得到一種算式方案。例如：S = A1 A2 A3 A4，K = 2，則 S = (A1) A2 (A3 A4) 就是一種算式方案。而對任意兩個算式方案，S和 S本質(zhì)不同是指：存在某數(shù)列 A1，A2An 滿足S S。否則就是本質(zhì)相同。例如：S = (A1) A2 (A3 A4) 與 S = (A1 A2) (A3 A4)就是本質(zhì)相同的算式方案。現(xiàn)在，F(xiàn)armer John 告訴奶牛 Besty 算式中項的個數(shù) N 和括號的個數(shù) K（數(shù)列 A 是變量，不需要關(guān)心它），他想考考 Besty 究竟有多少本質(zhì)不同的算式方案。輸入文件輸入文件名：count.in輸入文件僅一行，依次

5、為兩個整數(shù) N 和 K。（1 N , K 100）輸出文件輸出文件名：count.out輸出文件僅一行，為本質(zhì)不同的算式方案數(shù)。樣例輸入4 1樣例輸出4節(jié)問題描述明天就是 2 月 14 日的了。本來是一件令人高興地事，但 John 卻為明天的節(jié)而非常煩惱。John 走遍了各個商店，但沒有一件正當他將要失去信心時，電視中的一個能使他滿意的，他覺得那些都缺乏新意。引起了他的注意?！斑@里是 XX，明，。我天就是節(jié)了，的周末將在明出節(jié)特別鮮花獻給有請各位觀眾趕快撥打的，前 30 對撥打的觀眾將會有機會在現(xiàn)場參們的們這次的內(nèi)容有”其中有一個是：將從天上撒下許多鮮花，而參加節(jié)目的觀眾可以推著一個小車，來回

6、移動以接住這些鮮花，最后將根據(jù)你所得到的鮮花決定獲得的，而你所獲得的鮮花也可以全部歸自己所有，送給自己心愛的人。獎品倒是無所謂，John 知道他的女朋友是很喜歡鮮花的，特別是有這么多各式各樣的品種。John 于是馬上撥打了的號碼。竟然剛好是第 30 位，他太幸運了。為了珍惜這次難得的機會，John 發(fā)誓他一定要獲得大獎。通過對這個過程的分析，John 發(fā)現(xiàn)的場地可以劃分成 1*N 個方格，一開始你將站在第N div 2 個方格內(nèi)。每個時刻都可能有鮮花落下，而一旦鮮花，你將不能把它撿起來放進小車內(nèi)。由于小車有一定的重量，控制時并不是特別容易，你在每一時間能讓小車的速度加 1，減 1 或者不變。假設(shè)你當前的位置是 5，速度是 7，下一時間內(nèi)只你的位置將只能是 11,12 或者 13，對應(yīng)的速度將分別是 6,7,8。與此同時，每朵鮮花也有著不同的分值。獲得最高的分值總和就是最終的目的。輸入輸出文件輸入文件為 flower.in，文件的第一行有三個整數(shù) N,M,V(N=100,M=1000000,1=V=5),分別表示場地的寬的度和掉落鮮花數(shù)和移動速度。接下來M 行，每行有三個整數(shù) i,j,k，按照鮮花時間，位置和分值。時間的先后順序，給出了鮮花的輸出文件為 flower.out，第一行為你的程序得到的最大分值總和，接下來每行