#2147. [GESP202406 四级] 宝箱

    ID: 2147 Type: Default 1000ms 256MiB Tried: 26 Accepted: 2 Difficulty: 2 Uploaded By: Tags>分支结构动态规划 DP背包 DP

[GESP202406 四级] 宝箱

{"zh":"## Description\n\n荔枝发现了 nn 个宝箱,其中第 ii 个宝箱的价值是 aia_i 。\n\n荔枝可以选择一些宝箱放入背包并带走,但是荔枝的背包比较特殊,假设荔枝选择的宝箱中最大价值为 xx ,最小价值\n为 yy ,荔枝需要保证 x-y \\leq k ,否则荔枝的背包会损坏。\n\n荔枝想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。\n\n\n## Input Format\n\n第一行包含两个正整数 n,kn,k ,含义如题面所示。\n\n第二行包含 nn 个正整数 a1,a2,...,ana_1,a_2,...,a_n ,代表宝箱的价值。\n\n## Output Format\n\n输出一个整数,代表带走宝箱的最大总价值。\n\n\ninput1\n5 1\n1 2 3 1 2\n\n\n\noutput1\n7\n\n\n\n## Hint\n\n### 样例解释\n\n在背包不损坏的情况下,荔枝可以拿走两个价值为 22 的宝箱和一个价值为 33 的宝箱。\n\n### 数据范围\n\n对于全部数据,保证有 $1 \\leq n \\leq 1000,0 \\leq k \\leq 1000,1 \\leq a_i \\leq 1000$ 。\n\n\n## Source\n\nGESP四级202406"}