题目名称	350. 小吃店
输入输出	`food.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cqw 于2009-07-08加入
开放分组	全部用户
提交状态
分类标签	动态规划背包问题
	分享题解

通过：80，提交：180，通过率：44.44%
Pom	100	0.232 s	24.13 MiB	C++
stone	100	0.238 s	24.18 MiB	C++
.Xmz	100	0.300 s	24.13 MiB	C++
0-0	100	0.376 s	24.03 MiB	Pascal
苏轼	100	0.397 s	24.03 MiB	Pascal
天下第一的吃货殿下	100	0.398 s	24.03 MiB	Pascal
TBK	100	0.442 s	27.01 MiB	C++
不列颠呆毛	100	0.444 s	27.01 MiB	C++
kaaala	100	0.458 s	24.13 MiB	C++
digital-T	100	0.515 s	24.39 MiB	C++

关于小吃店的近10条评论(全部评论)
没有一A，身败名裂 Hale 2019-06-04 13:31 10楼
智障一样，又忘记开文件读写了 HeHe 2017-03-06 10:31 9楼
千万要听话，不要开long long ，否则T成翔 Hzoi_Go灬Fire 2016-10-11 07:40 8楼
不优化可以过，代价是总时间2s多 O(1) 2016-03-10 17:48 7楼
惊了。。。（掀桌 raywzy 2015-09-30 09:32 6楼
二维费用背包+背包方案总数乌龙猹 2014-10-31 21:32 5楼
看到各位大神的评论顿时吓尿。。然后写了个裸背包就过了 HouJikan 2014-08-28 18:27 4楼
居然没神牛写个题解，让我等弱菜怎么活囧~ 共需要控制两个循环上界下界的两个优化（共三个循环，简单DP），神奇的是，因为有两层循环，优化全加速度会快上几十倍（乘积效应），只加其中任一个仍然会超时。天下第一的吃货殿下 2012-10-21 18:14 3楼
如果不是数据过大，这题就是类似背包的水题，需要加优化，我的勉强过了。。。 QhelDIV 2012-10-13 23:59 2楼
销魂题目 Pom 2011-03-18 11:24 1楼

350. 小吃店

★☆ 输入文件：food.in 输出文件：food.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目背景】

小白终于决定了去小吃店的方案。来到小吃店的小白被琳琅满目的小吃看得直流口水。他对自己说：我一定要把钱全部用来买小吃！！但是小白最近在减肥，所以他不希望吃太多，他给自己又定了一个量，他希望正好达到这个量，不能多也不能少。假设每种最多买一份。

【题目描述】

给出 $n$ 个数对（$a_i$，$b_i$），每个数对都满足 $a_i \geq b_i$。要求在这 $n$ 个数对中选出 $k$ 对，使得 $a_{i1}+a_{i2}+a_{i3}+……+a_{ik}=m$ 且 $b_{i1}+b_{i2}+b_{i3}+……+b_{ik}=w$，$k$ 为任意数，有几种方案。

【输入格式】

第一行有三个整数 $n,m,w$。

接下来 $n$ 行每行二个整数 $a_i,b_i$。

【输出格式】

方案总数。

【样例输入】

【样例输出】

【样例说明】

$(1,3)$、$(2)$ 和 $(3，4)$ （这里的数字表示第几对）

【数据规模与约定】

对于 $30\%$ 数据,$0 \leq n \leq 10,0 \leq m,w \leq 100$

对于 $100\%$ 数据,$0 \leq n \leq 50,0 \leq m,w \leq 2,500$

对于 $100\%$ 数据，$0 \leq a_i,b_i \leq 100$

保证运算和输出不会超过 $long$ $long$

【来源】

cogs