POJ 1007 DNA Sorting（待改善）

POJ 1007 DNA Sorting

这道题做的不舒服，明白题目的意思后就想到一种最笨的解题思路——双重 for 循环来计算 DNA 序列的数值（左边字母大于右边字母的总个数）。但我始终觉得这不是好的算法，隐约觉得应该用“动态规划”。可惜学艺不精，一直没明白动态规划的原理。标记出来，期望改善之。

?

双重 for 循环的做法很快就实现了，开始使用 TreeMap 来存储数据，期望使用它的排序功能。结果忽略了值相等的情况，老是报 WA。所以改成将值拼凑入 DNA 序列开头的做法，并自定义 compare 方法进行比较。

代码如下：

import java.util.Scanner;import java.util.List;import java.util.ArrayList;import java.util.Iterator;import java.util.Comparator;import java.util.Collections;public class Main {private List<String> dnaList;public int countValue(String dna) {int value = 0;char[] c = dna.toCharArray();for (int i = 0; i < c.length; i++) {for (int j = i + 1; j < c.length; j++) {if (c[i] > c[j]) {value++;}}}return value;}public void run() throws Exception {Scanner scan = new Scanner(System.in);int n = scan.nextInt(); // string lengthint m = scan.nextInt(); // lines limitdnaList = new ArrayList<String>(m);scan.nextLine();for (int i = 0; i < m; i++) {String dna = scan.nextLine();int count = countValue(dna);dnaList.add((char)count + dna);}// sortCollections.sort(dnaList, new Comparator<String>() {public int compare(String o1, String o2) {return o1.charAt(0) - o2.charAt(0);}});// outputIterator<String> iter = dnaList.iterator();while (iter.hasNext()) {String dna = iter.next();System.out.println(dna.substring(1, dna.length()));}}public static void main(String[] args) {Main m = new Main();try {m.run();} catch (Exception e) {e.printStackTrace();}}}