題目來(lái)源：基因工程

解題思路：假設(shè)基因序列長(zhǎng)度為N，則需要計(jì)算基因序列前K個(gè)和后K個(gè)相同所需要的最少改變次數(shù)sum。

假設(shè)基因序列為 ATACGTCT （即M=8），K=6；interval=M-K=2；

? ? ? ? ?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7

sq1 ? ?A ?T ?A C ?G ?T ?C ?T

?

sq2 ? ?A ?C G?T ??C ?T?

從上圖可以看出，標(biāo)有相同彩色的字符相同，sq1的下標(biāo)為0的字符與sq2的下標(biāo)為0的字符相同，即 sq1[0]==sq1[2]，由此可以得出sq1[i]==sq1[i+interval],其中0<=i<=interval，因此此題可以轉(zhuǎn)化為求要想使字符 sq1[i],sq1[i+interval],sq1[i+interval*2],... 全部變成相同字符，需要改變多少次。解決這個(gè)問(wèn)題就很簡(jiǎn)單了，只需要分別統(tǒng)計(jì)所有字符出現(xiàn)的次數(shù)，然后用總數(shù)total減去字符出現(xiàn)最多的次數(shù)max，即temp=total-max；最后將所有的temp求和。

具體算法（Java版，直接AC）

1 import java.util.Scanner; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 Scanner scanner = new Scanner(System.in); 7 int T = scanner.nextInt(); 8 while (T > 0) { 9 String gene = scanner.next(); 10 int K = scanner.nextInt(); 11 int interval = gene.length() - K; 12 int sum = 0; 13 for (int i = 0; i < interval; i++) { 14 int[] count = new int[4];//用來(lái)統(tǒng)計(jì)出現(xiàn)的次數(shù) 15 for (int j = i; j < gene.length(); j += interval) { 16 if (gene.charAt(j) == 'A') { 17 count[0]++; 18 } else if (gene.charAt(j) == 'T') { 19 count[1]++; 20 } else if (gene.charAt(j) == 'C') { 21 count[2]++; 22 } else if (gene.charAt(j) == 'G') { 23 count[3]++; 24 } 25 } 26 int total = 0, max = 0; 27 for (int j = 0; j < 4; j++) { 28 total += count[j]; 29 max = max > count[j] ? max : count[j]; 30 } 31 sum += total - max; 32 } 33 System.out.println(sum); 34 T--; 35 } 36 } 37 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/pinxiong/p/4082592.html

總結(jié)

以上是生活随笔為你收集整理的hihoCoder 1052 基因工程 最详细的解题报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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