hdu 1250 hdu 1130 java水大数

HDU1160是一个经典的动态规划问题，题目描述如下： 给定一组老鼠的体重和速度，要求找出最长的老鼠序列，使得序列中每只老鼠的体重和速度都严格递增。 我们可以使用动态规划来解决这个问题。具体步骤如下： 1. 将老鼠按体重或速度排序。 2. 使用动态规划数组`dp`，其中`dp[i]`表示以第`i`只老鼠结尾的最长序列长度。 3. 使用一个数组`pre`来记录每个位置的前驱老鼠，以便最后可以重建序列。 以下是使用Java实现的代码： ```java import java.util.*; class Mouse implements Comparable<Mouse> { int weight, speed, index; Mouse(int weight, int speed, int index) { this.weight = weight; this.speed = speed; this.index = index; } public int compareTo(Mouse other) { if (this.weight != other.weight) { return this.weight - other.weight; } else { return this.speed - other.speed; } } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); List<Mouse> mice = new ArrayList<>(); while (scanner.hasNext()) { int weight = scanner.nextInt(); int speed = scanner.nextInt(); mice.add(new Mouse(weight, speed, mice.size())); } scanner.close(); Collections.sort(mice); int n = mice.size(); int[] dp = new int[n]; int[] pre = new int[n]; int maxLen = 1, endIndex = 0; Arrays.fill(pre, -1); Arrays.fill(dp, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (mice.get(i).weight > mice.get(j).weight && mice.get(i).speed > mice.get(j).speed) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; pre[i] = j; } } } if (dp[i] > maxLen) { maxLen = dp[i]; endIndex = i; } } List<Integer> sequence = new ArrayList<>(); while (endIndex != -1) { sequence.add(mice.get(endIndex).index + 1); endIndex = pre[endIndex]; } System.out.println(maxLen); for (int i = sequence.size() - 1; i >= 0; i--) { System.out.println(sequence.get(i)); } } } ```