题目来自蓝桥云

// 这是一个Java程序，用于解决最长不下降子序列问题。
// 问题描述：给定一个整数序列，找到最长的子序列，使得这个子序列是不下降的（即相邻的元素不严格递减）。
// 程序使用了动态规划的方法来解决这个问题。

import java.util.*;

public class Main {
    // n表示序列的长度，m表示背包的容量
    static int n, m;
    // w和t分别表示物品的重量和价值
    static int[] w = new int[256];
    static int[] t = new int[256];
    // dp数组用于存储动态规划的结果
    static long[] dp = new long[1010];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读入序列的长度和背包的容量
        n = sc.nextInt();
        m = sc.nextInt();
        // 读入序列中的每个元素的重量和价值
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
            t[i] = sc.nextInt() * 1000; // 将时间单位转换为毫秒
        }
        // 使用二分查找法寻找满足条件的最大整数解
        int l = 0, r = 25000000;
        while (l + 1 != r) {
            int mid = l + (r - l) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        // 输出满足条件的最大整数解
        System.out.println(l);
    }

    // 检查给定速度下是否能完成任务
    public static boolean check(int x) {
        Arrays.fill(dp, -25000000L);
        dp[0] = 0;
        // 遍历物品，更新动态规划表
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= 0; j--)
                // 选择放置或不放置物品
                dp[Math.min(j + w[i], m)] = Math.max(dp[Math.min(j + w[i], m)], dp[j] + t[i] - (long) w[i] * x);
        // 判断是否能完成所有任务
        return dp[m] >= 0;
    }
}