[蓝桥杯 2022 国 B] 费用报销

Luogu

IDLGP8803

Time1000ms

Memory128MB

DifficultyP4

动态规划 DP2022蓝桥杯国赛

小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 $K$ 天，且总金额不得超过实际差旅费用 $M$。比如财务要求 $K=7$ 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票据，1 月 1 日及之前和 1 月 15 日及之后的票据则可以提交。公司的同事们一起给小明凑了 $N$ 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据, 并使总金额尽可能接近 $M$ 。需要注意，由于这些票据都是同一年的，因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。 ## Input 第 $1$ 行：$3$ 个整数, $N, M, K$。第 $2 \ldots N+1$ 行：每行 3 个整数 $m_{i}, d_{i}, v_{i}$, 第 $i+1$ 行表示第 $i$ 张票据时间的月份 $m_{i}$ 和日期 $d_{i}$，$v_{i}$ 表示该票据的面值。 ## Output 第 $1$ 行：$1$ 个整数, 表示小明能够凑出的最大报销金额。 [samples] ## Note **【样例说明】** 选择 1 月 3 日和 1 月 6 日的票据 **【评测用例规模与约定】** 对于 $100 \%$ 的评测用例, $1 \leq N \leq 1000,1 \leq M \leq 5000,1 \leq K \leq 50,1 \leq m_{i} \leq$ $12,1 \leq d_{i} \leq 31,1 \leq v_{i} \leq 400$ 日期保证合法。蓝桥杯 2022 国赛 B 组 F 题。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2022 国 B] 费用报销",
    "description": {
      "content": "小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。 为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 $K$ 天，且总金额不得超过实际差旅费用 $M$。 比如财务要求 $K=7$ 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8803"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。\n\n为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 $K$ 天，且总金额不得超过实际差旅费用 $M$。\n\n比如财务要求 $K=7$ 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments