信息學(xué)集訓(xùn)隊(duì)作業(yè)0070-dna

題目0070–DNA（DNA序列密碼問(wèn)題）題目來(lái)源：Other推薦者：許智磊英文原文二、中文翻譯DNA序列密碼問(wèn)題問(wèn)題描述： 一些生物的復(fù)雜結(jié)構(gòu)可以用其DNA序列來(lái)表示。而DNA序列又可表示為帶有標(biāo)記的核苷酸字符串。最近，福州大學(xué)信息學(xué)院生物信息學(xué)研究小組的一項(xiàng)工作表明，大多數(shù)蛋白質(zhì)序列可以從核苷酸數(shù)據(jù)庫(kù)記錄中推導(dǎo)出來(lái)。研究小組的科學(xué)家們用密碼學(xué)方法將DNA序列變換為2維Cray碼后發(fā)現(xiàn)，任一DNA的Cray碼序列S具有如下性質(zhì)：列S：（x1，y1），（x2，y2），…，（xn，yn）是一個(gè)有限序列；列S中各項(xiàng)（xi，yi）均落在一個(gè)網(wǎng)格邊長(zhǎng)為1的300×3000平面網(wǎng)格N的網(wǎng)格點(diǎn)上；3．序列S中各項(xiàng)最多分布在網(wǎng)格N的3行中?？茖W(xué)家們發(fā)現(xiàn)，若將序列S的每一項(xiàng)都看作平面上一個(gè)點(diǎn)，從序列的任意一點(diǎn)出發(fā)，連接序列中每個(gè)點(diǎn)恰好一次，又回到出發(fā)點(diǎn)的最短平面回路T的長(zhǎng)度與該序列表示的DNA密碼密切相關(guān)。為了有效地破譯DNA密碼，科學(xué)家們希望設(shè)計(jì)出一個(gè)高效的計(jì)算程序，能對(duì)給定DNA的Cray碼序列S，快速計(jì)算出其最短回路T的長(zhǎng)度。 編程任務(wù)：對(duì)于給定的DNA的Cray碼序列S，計(jì)算出其最短回路T的長(zhǎng)度。數(shù)據(jù)輸入：Cray碼序列S依其在網(wǎng)格N中的位置分為3行：(a1,ya),(a2,ya),…,(ana,ya);(b1,yb),(b2,yb),…,(bnb,yb);(c1,yc),(c2,yc),…,(cnc,yc)。其中0≤ya<yb<yc≤300分別是3行的縱坐標(biāo)。0≤na，nb，nc≤1300；分別是各行中的點(diǎn)數(shù)。各行中點(diǎn)依其橫坐標(biāo)從小到大排列。0≤a1<a2<…<ana≤3000;0≤b1<b2<…<bnb≤3000；0≤c1<c2<…<cnc≤3000.輸入數(shù)據(jù)由文件名為INPUT3.*的文本文件提供?！竦?行中的3個(gè)整數(shù)為na，nb和nc； ●第2行中的3個(gè)整數(shù)為ya，yb和yc；●接下來(lái)的na行中每行一個(gè)整數(shù)，依次為a1，a2，…，ana；●再接下來(lái)的nb行中每行一個(gè)整數(shù)，依次為b1，b2，…，bnb；●最后的nc行中每一個(gè)整數(shù)，依次為c1，c2，…，cnc。 結(jié)果輸出程序運(yùn)行結(jié)束時(shí)，在屏幕上輸出所找到的序列S的最短回路T的長(zhǎng)度值，精確到小數(shù)點(diǎn)后2位。輸入文件示例 輸出示例 INPUT3.001 8.832121235 7657三、初步討論情況姜尚仆動(dòng)態(tài)規(guī)劃方奇動(dòng)態(tài)規(guī)劃高正宇動(dòng)態(tài)規(guī)劃陸可昱四邊形不等式??項(xiàng)榮璟感覺(jué)可以用動(dòng)態(tài)規(guī)劃，可能要分幾種情況，比較麻煩。還沒(méi)想清楚。伍昱應(yīng)該可以用動(dòng)態(tài)規(guī)劃好像還可以用四邊形不等式加速邵煊程由于最短回路有一定的構(gòu)形，因此可以用動(dòng)態(tài)規(guī)劃解決。張?jiān)屏烈驗(yàn)橹挥腥校钥梢杂脛?dòng)態(tài)規(guī)劃，看中間一行的點(diǎn)是屬于找出哈密爾頓回路的上分支還是下分支。雷環(huán)中目前不會(huì)做。已知一種O(N^3)的動(dòng)態(tài)規(guī)劃算法，最后一個(gè)測(cè)試點(diǎn)可以3秒鐘出解（時(shí)限60秒），不過(guò)算法實(shí)現(xiàn)起來(lái)比較麻煩，肯定有更好的算法。許智磊最短的路肯定沒(méi)有交叉，所以先求外圍輪廓，然后在某些地方凹進(jìn)去，采用動(dòng)態(tài)規(guī)劃，而且可以用四邊形不等式來(lái)優(yōu)化。劉才良回路不能自交，否則不是最優(yōu)，由此可以看出問(wèn)題主要就在第二行的點(diǎn)的安排，這個(gè)可以用動(dòng)態(tài)規(guī)劃解決，時(shí)間復(fù)雜度O(N3)張寧利用幾何性質(zhì)，我們可以用動(dòng)態(tài)規(guī)劃解決此題，并且可以利用四邊形不等式，我們可以把時(shí)間復(fù)雜度從O(n^3)降到O(n^2)林希德DP好了，四邊形優(yōu)化后復(fù)雜度可以從O(n3)降到O(n2)王知昆在平面上的最優(yōu)哈密爾頓回路一定不存在兩條邊相交。利用這個(gè)性質(zhì)可以設(shè)計(jì)出動(dòng)態(tài)規(guī)劃算法。首先，求凸包（實(shí)際上就是將1，3兩行的點(diǎn)和第二行頭尾兩個(gè)點(diǎn)串起來(lái)），然后對(duì)于第二行中的每一個(gè)點(diǎn)，判斷它的連接方案。有兩種情況，一是從第二行它前面的點(diǎn)連接到它，二是從凸包上的一個(gè)點(diǎn)連接到它。這樣可以用動(dòng)態(tài)規(guī)劃解決社d[i]表示第二行前i個(gè)點(diǎn)（如果第一個(gè)點(diǎn)在凸包上，就要把第一個(gè)點(diǎn)除去）連接到凸包上的最小距離和。d[i]=min(d[j]+s[i,j,k]),j<i說(shuō)明：s[i,j,k]表示將第二行中的點(diǎn)i到點(diǎn)j連接到凸包的第k個(gè)點(diǎn)和第k＋1個(gè)點(diǎn)之間的長(zhǎng)度。劉一鳴題目中的Hamilton回路可以用兩條不相交的路徑來(lái)表示（若相交一定不是最優(yōu)解）。令一條路徑連結(jié)第1行的點(diǎn)和第2行的若干個(gè)點(diǎn)，另一條路徑連結(jié)第3行的點(diǎn)第2行的其它點(diǎn)。---*--*--\\---*+---*--\\*----------問(wèn)題的關(guān)鍵就在于第2行的安排。如上圖，在“+”表示的點(diǎn)的左側(cè)第2行的點(diǎn)在第1條路徑中，右側(cè)在第2條路徑中。由此，假設(shè)第2行的點(diǎn)數(shù)為n，設(shè)f[n,k]（1<=k<=2）表示第2行的第n個(gè)點(diǎn)由第k條路徑來(lái)連之前的最優(yōu)值?？梢缘玫綘顟B(tài)轉(zhuǎn)移方程：f[n,k]=min{f[i,3-k]+cost[i,3-k,n,k]}cost[i,3-k,n,k]表示(i,3-k)到(n,k)狀態(tài)值的差，也就是中間點(diǎn)的總路程。這個(gè)值可以在預(yù)處理的時(shí)候算出來(lái)。由狀態(tài)轉(zhuǎn)移方程不難看出，DP的時(shí)間復(fù)雜度是O(n2)。金愷由于最短Hamilton回路（以下簡(jiǎn)稱H）滿足一個(gè)特性：任意兩條邊都不相交，再加上本題特殊的條件：所有點(diǎn)都處于3行上，所以H的外形是很有特點(diǎn)的（如右圖）：可以看成將凸包的某些邊凹進(jìn)去形成的一條回路，而且凹進(jìn)去的是一個(gè)個(gè)的梯形（三角形可以看成某底邊長(zhǎng)為0的梯形）。因此，H的長(zhǎng)度=凸包的邊長(zhǎng)+某些邊凹進(jìn)去時(shí)增加的長(zhǎng)度，要使H的長(zhǎng)度最小，也就是使增加的長(zhǎng)度最小，同時(shí)還要保證中間一排的點(diǎn)都在H上。利用這些特點(diǎn)可以采用動(dòng)態(tài)規(guī)劃來(lái)解決：設(shè)Fi表示第二排中，前i個(gè)點(diǎn)都以連接到了H上，最少需要新增的長(zhǎng)度，顯然有Fi=Fj–1+(X2,i–X2,j)+Min{Dis(X2,j,Y2,X1,k,Y1)+Dis(X2,i,Y2,X1,k+1,Y1),Dis(X2,j,Y2,X3,k,Y3)+Dis(X2,i,Y2,X3,k+1,Y3)}上述方程中有兩個(gè)未知量j、k，但k的確定是滿足四邊形不等式的，因此總的復(fù)雜度為O(N2)。饒向榮很明顯，我們可以先將路線定為圍著第一行和第三行的所有點(diǎn)形成的環(huán)，然后可對(duì)此環(huán)作凹入處理，使得環(huán)包括第二行上的點(diǎn)，而且凹入的各部分之間比不相交，也就是說(shuō)前面的凹入對(duì)后面無(wú)影響，即無(wú)后效性，那么考慮用動(dòng)態(tài)規(guī)劃，表示第二行的前個(gè)點(diǎn)都被凹入的最短路，那么狀態(tài)轉(zhuǎn)移方程為：f[i]=min{f[j-1]+mc[j,i],1≤j≤i}其中的表示對(duì)第二行的第j個(gè)點(diǎn)到第i個(gè)點(diǎn)凹入的最短方案值，這個(gè)可以提前算出來(lái),它的計(jì)算滿足四邊形不等式，時(shí)間復(fù)雜度為O(N2)。此算法的總復(fù)雜度為O(N2)。何林凡是這類平面點(diǎn)的hamilton問(wèn)題，都有一個(gè)重要的性質(zhì)：連線不相交。證明很容易，略去。因此先把凸包求出來(lái)（這個(gè)題凸包很特殊，所以O(shè)(n)就能簡(jiǎn)單的搞定）。凸包必然包含上、下兩條與x軸平行的邊。（也就是題目中點(diǎn)分布的上下兩