[CSP-X2021 山东] 发送快递

Luogu
IDLGB4093
Time1000ms
Memory512MB
DifficultyP4
搜索2021山东CSP-X 小学组状压 DP
小华有 $n$ 本不同的书(编号为 $1,2,3,\dots,n$),重量分别是 $a_1,a_2,\dots,a_n$ 公斤(重量可以相同)。他想把这些书以快递的方式发给自己的好朋友,要求每个包裹的重量不能超过 $m$ 公斤(可以等于 $m$ 公斤),并且小华想把其中一些书(一组书,用书的编号给出来)放在一个包裹里,应该如何打包才能使得快递件数最少。 ## Input 第一行,包含两个整数 $n,m$,之间用一个空格隔开,分别表示书的数量和快递包裹的最大重量。 第二行 $n$ 个整数 $a_i$,表示 $n$ 本书的重量,每两个整数之间用一个空格隔开。 第三行一个整数 $s$,表示一共有 $s$ 组书(每组书需要打包在一起)。如果 $s=0$,则无此限制。数据保证每组书的重量不超过 $m$。 第四行开始共 $s$ 行,每行若干个整数,表示必须放在一个包裹里的书的编号,每两个整数之间用一个空格隔开。 ## Output 输出文件一行,一个整数,即快递最少件数。 [samples] ## Background **原题为错题,不可做。数据范围修改如下,请以题目背景中的为准:** 【数据范围和限制】 对于 $40\%$ 的数据,$1 \leq n \leq 23$,$1 \leq a_i \leq 100$,$s=0$,$m$ 的值保证有解。 对于 $100\%$ 的数据,$1 \leq n \leq 23$,$1 \leq a_i \leq 100$,$0 \leq s \leq 15$,$m$ 的值保证有解。 **为了防止无意义的钻牛角尖的 hack,本题认为 $m$ 不超过 $2^{31}-1$。** ## Note 【输入输出样例 1 说明】 第 $1$ 本和第 $4$ 本打包,重量是 $10$ 公斤。第 $2$ 本和第 $5$ 本打包,重量是 $9$ 公斤。第 $3$ 本单独打包,重量是 $8$ 公斤。所以一共 $3$ 件快递。 【输入输出样例 2 说明】 第 $1$ 本和第 $5$ 本打包,第 $2$ 本、第 $4$ 本、第 $8$ 本和第 $10$ 本打包,第 $3$ 本和第 $7$ 本打包,第 $6$ 本和第 $9$ 本打包。所以一共 $4$ 件快递。 【数据范围和限制】 对于 $40\%$ 的数据,$1 \leq n \leq 10^5$,$1 \leq a_i \leq 100$,$s=0$,$m$ 的值保证有解。 对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$1 \leq a_i \leq 100$,$0 \leq s \leq 100$,$m$ 的值保证有解。
Samples
Input #1
5 10
8 4 8 2 5
0
Output #1
3
Input #2
10 80
49 11 44 18 28 24 19 10 27 29
2
1 5
4 8 2
Output #2
4
API Response (JSON)
{
  "problem": {
    "name": "[CSP-X2021 山东] 发送快递",
    "description": {
      "content": "小华有 $n$ 本不同的书(编号为 $1,2,3,\\dots,n$),重量分别是 $a_1,a_2,\\dots,a_n$ 公斤(重量可以相同)。他想把这些书以快递的方式发给自己的好朋友,要求每个包裹的重量不能超过 $m$ 公斤(可以等于 $m$ 公斤),并且小华想把其中一些书(一组书,用书的编号给出来)放在一个包裹里,应该如何打包才能使得快递件数最少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4093"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小华有 $n$ 本不同的书(编号为 $1,2,3,\\dots,n$),重量分别是 $a_1,a_2,\\dots,a_n$ 公斤(重量可以相同)。他想把这些书以快递的方式发给自己的好朋友,要求每个包裹的重量不能超过 $m$ 公斤(可以等于 $m$ 公斤),并且小华想把其中一些书(一组书,用书的编号给出来)放在一个包裹里,应该如何打包才能使得快递件数最少。\n\n## Input\n\n第一行,包含两个整数 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments