1s / 32M

【問題描述】
目前,科學家們正致力于對生物基因的重組進行深入研究。基因的物質(zhì)載體是脫氧核糖
核酸(DNA)
。DNA 是一種僅由 A、T、G、C 四種基元構(gòu)成的雙螺旋結(jié)構(gòu)的有機分子。
DNA 的兩條單鏈上,同一位置的兩個基元是互相對應(yīng)的。A 對 T,G 對 C,因此,我們
只需用任意一條鏈上的基元排列,就可以表示 DNA 的分子結(jié)構(gòu)。例如:ATTGAGCCGTAT。
由于 DNA 微小而復雜,重組 DNA 極其困難,科學家們打算利用一條現(xiàn)成的 DNA 鏈作原
材料拼接成另外一條新的 DNA 鏈。即使這樣,拼接 DNA 仍然是一件繁重的工作,非人力所
能勝任。所以科學家們制造了一種手術(shù)機器人 TuringM 來完成這項任務(wù)。TuringM 每次只能
在目標鏈(T)的右端與原材料 (S) 的左端進行操作。它有下列幾種基本拼接操作:

對于每種操作,機器人的單位時間耗費如上表所示(單位:分鐘)
。最后剩余的原材料
自動丟棄。現(xiàn)在的任務(wù)是請你編一個程序,幫助科學家們找出完成 DNA 鏈拼接的最少時間。
從 S 的左端切下
一段(一對或多
對)直接或上下
翻轉(zhuǎn)后拼接到 T
的右端上
【輸入格式】
輸入文件包括三行,第一行是三個數(shù) c1、c2、c3。
二、三兩行每行一個字符串,分別表示原材料 DNA 與目標 DNA 鏈的上半部分。
【輸出格式】
輸出文件只有一行,表示拼接出目標 DNA 的最小時間。
【輸入輸出樣例】
3 2 3
CCGATGTATCTG
TACGATCGGTC

輸出

23
【數(shù)據(jù)規(guī)模】
DNA 鏈的長度不超過 5000
最少時間不會超過 10 天。

令f[i][j][0/1]表示原材料消除j個，目標構(gòu)成i個

最后一次是1操作(0/1對應(yīng)正反)

f[i][j][2]表示最后一次是2操作

f[i][j][3]表示最后一次是3操作

于是有:

f[i+1][j][3]=min(f[i][j][0~3])+c3???? (給結(jié)果材料加一位)

f[i][j+1][2]=min(f[i][j][2],min(f[i][j][0,1,3])+c2)

(刪掉一位原材料,前一個表示把這次操作和上一個2操作合并)

f[i+1][j+1][0/1]=min(f[i][j][0/1],min(f[i][j][0~3])+c1)

(表示刪掉一位原材料，加入結(jié)果材料，要求必須原材料j位和目標材料i位要匹配)

初始化直接f[0][0][3]就行了，因為3操作只能加一位，不能與前面的3合并

所以就相當于初始無操作

內(nèi)存不夠，要滾動數(shù)組

%%%%%%YZD巨佬

1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 int a1[5005],a2[5005],f[2][5005][5],c1,c2,c3,now,nxt,n,m,inf,ans; 8 char s[5005]; 9 int main() 10 {int i,j; 11 cin>>c1>>c2>>c3; 12 cin>>s; 13 m=strlen(s); 14 for (i=0;i<m;i++) 15 if (s[i]=='A') a1[i+1]=0; 16 else if (s[i]=='T') a1[i+1]=1; 17 else if (s[i]=='C') a1[i+1]=2; 18 else if (s[i]=='G') a1[i+1]=3; 19 cin>>s; 20 n=strlen(s); 21 for (i=0;i<n;i++) 22 if (s[i]=='A') a2[i+1]=0; 23 else if (s[i]=='T') a2[i+1]=1; 24 else if (s[i]=='C') a2[i+1]=2; 25 else if (s[i]=='G') a2[i+1]=3; 26 now=0;nxt=1; 27 memset(f,127/3,sizeof(f)); 28 inf=f[0][0][0]; 29 f[0][0][3]=0; 30 now=0;nxt=1; 31 for (i=0;i<n;i++) 32 { 33 for (j=0;j<=m;j++) 34 { 35 f[nxt][j][3]=min(f[nxt][j][3],min(min(f[now][j][0],f[now][j][1]),min(f[now][j][2],f[now][j][3]))+c3); 36 if (j!=m) 37 f[now][j+1][2]=min(min(f[now][j+1][2],f[now][j][2]),min(min(f[now][j][1],f[now][j][0]),f[now][j][3])+c2); 38 if (j!=m&&a1[j+1]==a2[i+1]) 39 { 40 f[nxt][j+1][0]=min(min(f[nxt][j+1][0],f[now][j][0]),min(min(f[now][j][1],f[now][j][2]),f[now][j][3])+c1); 41 } 42 if (j!=m&&((a2[i+1]^1)==a1[j+1])) 43 { 44 f[nxt][j+1][1]=min(min(f[nxt][j+1][1],f[now][j][1]),min(min(f[now][j][0],f[now][j][2]),f[now][j][3])+c1); 45 } 46 } 47 memset(f[now],127/3,sizeof(f[now])); 48 swap(now,nxt); 49 } 50 ans=inf; 51 for (i=0;i<=m;i++) 52 ans=min(ans,min(min(f[now][i][0],f[now][i][1]),min(f[now][i][2],f[now][i][3]))); 53 cout<<ans; 54 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Y-E-T-I/p/7730009.html

總結(jié)

以上是生活随笔為你收集整理的基因重组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。