算法分析实习-漂亮打印（动态规划）

import java.awt.*; import java.awt.event.*; import java.util.*; import javax.swing.JOptionPane; public class NicePrint_gui extends Frame implements TextListener, ActionListener { TextArea t; Label l; TextField tf; Button b; Panel p; int m; //the maximum length of a line NicePrint_gui() { super("漂亮打印"); t = new TextArea(); t.addTextListener(this); l = new Label("当前设定最大行宽为30字符（英文字母）"); tf = new TextField("30"); b = new Button("确定"); b.addActionListener(this); p = new Panel(); p.add(l); p.add(tf); p.add(b); add(p, BorderLayout.NORTH); add(t, BorderLayout.CENTER); addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } }); setBounds(200, 100, 497, 400); setVisible(true); validate(); t.requestFocus(); m = 30; } void pri(int[] p, int sp, int ep, String[] w, int dept) { int i; if (sp == 0) { for(i = sp; i < ep - 1; i ++) { t.append(w[i] + " "); } t.append(w[i] + "\n"); return; } else { pri(p, p[sp - 1], sp, w, dept + 1); for(i = sp; i < ep - 1; i ++) { t.append(w[i] + " "); } if (dept == 0) { t.append(w[i]); } else { t.append(w[i] + "\n"); } } } public void textValueChanged(TextEvent e) { //--CHECK START StringTokenizer chk = new StringTokenizer(t.getText(), "'\n'"); String strline = null; while (chk.hasMoreTokens()) { strline = chk.nextToken(); } if (strline.length() <= m) { return; } else if (strline.substring(strline.length() - 1).equals(" ") && !strline.substring(strline.length() - 2).equals(" ")) { return; } //--CHECK END niceprint(); } void niceprint() { int[] c; //arrange word[0:j] , the minimum cost int[] p; //arrange word[0:j] , the first word of last line int[] len; //length of word[i] int[][] linecost;//put word[i:j] in a line , the cost int n, //number of words ext, //put word[i:j] in a line , the extra blanks i, j, k; //--INPUT START String str = t.getText(); StringTokenizer ana = new StringTokenizer(str, " '\n'"); n = ana.countTokens(); String[] word = new String[n]; len = new int[n]; for (i = 0; i < n; i ++) { word[i] = ana.nextToken(); len[i] = word[i].length(); if (len[i] > m) { alert("单词超过最大长度！"); t.setText(""); return; } } //--INPUT END //--NICEPRINT START linecost = new int[n][n]; for (i = 0; i < n; i ++) { for (j = i; j < n; j ++) { linecost[i][j] = -1; } } c = new int[n]; p = new int[n]; for (i = 0; i < n; i ++) { ext = m - len[i]; for (j = i; j < n; j ++) { if (j == n - 1 && ext > 0) { linecost[i][j] = 0; } else { linecost[i][j] = ext * ext * ext; } if (ext < 0) { break; } if (i == 0) { c[j] = linecost[i][j]; } else { c[j] = c[i - 1] + linecost[i][j]; p[j] = i; for (k = j; ; k --) { if (k == 0) { if (linecost[k][j] < c[j] && linecost[k][j] >= 0) { c[j] = linecost[k][j]; p[j] = 0; } break; } if (c[k - 1] + linecost[k][j] < c[j] && linecost[k][j] >= 0) { c[j] = c[k - 1] + linecost[k][j]; p[j] = k; } } } if(j + 1 < len.length) { ext -= len[j + 1] + 1; } } } //--NICEPRINT END t.setText(null); pri(p, p[n - 1], n, word, 0); } void alert(String message) { JOptionPane.showMessageDialog(this, message, "警告", JOptionPane.ERROR_MESSAGE); } public void actionPerformed(ActionEvent e) { if (e.getSource() == b) { try { int n = m; m = Integer.parseInt(tf.getText()); if (m < 3) { m = n; alert("输入数字太小！"); } else if (m > 77) { m = n; alert("输入数字太大！"); } } catch (NumberFormatException ex) { alert("请输入数字！"); } if (t.getText().equals("") == false) { niceprint(); } l.setText("当前设定最大行宽为" + m + "字符（英文字母）"); t.requestFocus(); } } public static void main(String[] args) { new NicePrint_gui(); } }