3813743_tle.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private String[][] best = new String[101][101];
	private int[][] len = new int[101][101];
	private Scanner in;

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);
		String str;
		int length;

		str = in.next();
		length = str.length();
		for (int i = 0; i < length; i++) {
			len[i][i] = 1;
			best[i][i] = "" + str.charAt(i);
		}
		for (int l = 2; l <= length; l++) {
			for (int i = 0; i <= length - l; i++) {
				int  t = i + l - 1;
				String sub = str.substring(i, t + 1);
				len[i][t] = l;
				best[i][t] = sub;
				for (int j = i; j < i + l; j++) {
					int tmp = len[i][j] + len[j + 1][t];
					if (tmp < len[i][t]) {
						len[i][t] = tmp;
						best[i][t] = best[i][j] + best[j + 1][t];
					}
				}
				for (int j = 1; j < l; j++) {
					if (l % j == 0) {
						String ret = check(sub, l / j, j, i, i + j - 1);
						if (ret.length() < len[i][t]) {
							len[i][t] = ret.length();
							best[i][t] = ret;
							break;
						}
					}
				}
			}
		}
		System.out.println(best[0][length - 1]);
	}

	private String check(String sub, int t, int l, int a, int b) {
		String tmp = sub.substring(0, l);
		String ret = "";

		for (int i = 0; i < t; i++) {
			ret += tmp;
		}
		if (ret.equals(sub)) {
			return Integer.toString(t) + "(" + 
				(l < len[a][b] ? tmp : best[a][b]) + ")";
		}
		return sub;
	}
}