京东 · 动态规划 · 算法编程题
京东 动态规划 n ≤ 2000 时限 1 秒 / 256 MB

题目描述

小红正在参加笔试，已知笔试一共有 n 个编程题，每个编程题有若干个测试用例，小红获得的分数和通过的测试用例数量成正比。
对于一个题而言，小红可以写一个暴力算法获得部分分，这样相对的比较节省时间，另外她还可以直接尝试正解，这样可以获得满分，但需要花费更多的时间。
现在给定了总时间，以及每个题目暴力算法的用时和得分、正确算法的用时和得分。
请你帮小红规划一个做题方案，可以在有限的时间内获得更多分数。
建议python考生使用pypy提交！

输入输出

输入描述
第一行输入两个正整数 n,t ，代表题目数量，以及笔试的总时长。
接下来 n 行，每行输入四个正整数 t_i1,s_i1,t_i2,s_i2 ，分别代表小红写出正解的用时，正确算法的得分，小红写暴力算法的用时，暴力算法的得分。
1≤ n,t≤ 2000
1≤ t_i2≤ t_i1≤ 2000
1≤ s_i2≤ s_i1≤ 10^5
输出描述
输出一个长度为 n 的字符串，第 i 个字符代表第 i 道题的策略：
如果这道题写暴力算法，则用字符'B'表示；如果写正确算法，则用字符'A'表示；如果放弃此题（不耗时间，但这道题0分），则用'F'表示。
请务必保证总耗时不超过 t ，且总得分尽可能大。如果有多种做题方案都能拿到最高分数，输出任意一种即可。

样例共 1 组

样例 1 · 前两题写正解，第三题写暴力算法，这样总耗时为9，总得分为10+20+15=45。可以证明，这样安排是最优的。
输入
3 10
4 10 2 5
4 20 2 5
6 20 1 15
输出
AAB

算法解析依据充分

考点：动态规划

数据规模 n ≤ 2000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 2000，t ≤ 2000
  • 元素值域：s_i2 ≤ 1e5，s_i1 ≤ 1e5，t_i2 ≤ 2000（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。

思路框架（动态规划 通法 · 非本题专属）

  1. 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
  2. 写转移方程：当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序（保证用到的状态已算好）。
  4. 确定答案取哪个状态；数值大时全程取模。

实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。

复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
  • 初始化写错（尤其「恰好」与「至多」的初值差别）。
  • 遍历顺序与依赖方向不一致。

对照本题

  • 数据规模 n ≤ 2000，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 10 / 4 10 2 5 / 4 20 2 5 / 6 20 1 15 → 输出 AAB

前两题写正解，第三题写暴力算法，这样总耗时为9，总得分为10+20+15=45。可以证明，这样安排是最优的。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第三批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解