猫粮规划

Luogu
IDLGB3624
Time2000ms
Memory128MB
DifficultyP3
深度优先搜索 DFS剪枝
到中午了,机器猫要吃猫粮了。 机器猫掏出 $n$ 份食物,第 $i$ 份食物含有的能量为 $w[i]$。机器猫可以吃掉其中一些食物,获得这些食物的能量之和。 机器猫又不想变得太胖又不想变得太瘦,所以指定了一个目标区间 $[l, r]$。显然,可能有很多种选择食物的方式可以达成这个目标,因此机器猫想知道方案总数。 ## Input 第一行,三个正整数 $n, l, r$。 第二行,$n$ 个正整数,表示每一份食物含有的能量 $w[i]$。 ## Output 仅一行,一个整数,表示方案数。 [samples] ## Note #### 样例解释 所有方案如下: 选择食物 $1, 2, 4$,能量 $10+10+50 = 70$; 选择食物 $1, 3, 4$,能量 $10+20+50 = 80$; 选择食物 $2, 3, 4$,能量 $10+20+50 = 80$; 选择食物 $3, 4$,能量 $50+20 = 70$。 共 $4$ 种方案。 #### 数据规模与约定 对于 $50\%$ 的数据,满足 $n\leq 20$。 对于 $100\%$ 的数据,满足 $n\leq 40, 20\leq w[i] \leq 100, l\leq r \leq 300$。 提示:$w[i]$ 在范围内均匀随机生成。
Samples
Input #1
4 70 85
10 10 20 50
Output #1
4
API Response (JSON)
{
  "problem": {
    "name": "猫粮规划",
    "description": {
      "content": "到中午了,机器猫要吃猫粮了。 机器猫掏出 $n$ 份食物,第 $i$ 份食物含有的能量为 $w[i]$。机器猫可以吃掉其中一些食物,获得这些食物的能量之和。 机器猫又不想变得太胖又不想变得太瘦,所以指定了一个目标区间 $[l, r]$。显然,可能有很多种选择食物的方式可以达成这个目标,因此机器猫想知道方案总数。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3624"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "到中午了,机器猫要吃猫粮了。\n\n机器猫掏出 $n$ 份食物,第 $i$ 份食物含有的能量为 $w[i]$。机器猫可以吃掉其中一些食物,获得这些食物的能量之和。\n\n机器猫又不想变得太胖又不想变得太瘦,所以指定了一个目标区间 $[l, r]$。显然,可能有很多种选择食物的方式可以达成这个目标,因此机器猫想知道方案总数。\n\n## Input\n\n第一行,三个正整数 $n, l, r$。\n\n第二行,$n$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments