P1164 小A点菜

提交91.58k

通过46.24k

时间限制1.00s

内存限制128.00MB

提交答案加入题单复制题目

做题计划（首页）

个人题单

团队题单

保存

选择团队

保存

题目提供者洛谷

难度普及-

历史分数100

?提交记录??查看题解

题目背景

uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。

uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过uim由于买了一些书，口袋里只剩MM元(M \le 10000)(M≤10000)。

餐馆虽低端，但是菜品种类不少，有NN种(N \le 100)(N≤100)，第ii种卖a_iai?元(a_i \le 1000)(ai?≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待11秒。

输入格式

第一行是两个数字，表示NN和MM。

第二行起NN个正数a_iai?（可以有相同的数字，每个数字均在10001000以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

输入输出样例

输入 #1复制

4 4
1 1 2 2

输出 #1复制

说明/提示

2020.8.29，增添一组 hack 数据 by @yummy

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
#define int long long
const int N=1e4+10;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void fwrite(int n)
{
	if(n>9)fwrite(n/10);
	putchar(n%10+'0');
}
int n,m,a[N],f[110][N],ans;
int find(int m,int x)
{
	if(f[m][x])return f[m][x];
	if(a[m]>x)return 0;
	if(a[m]==x)return 1;
	for(int i=m+1;i<=n;i++)f[m][x]+=find(i,x-a[m]);
	return f[m][x];
}
signed main()
{
	n=fread(),m=fread();
	for(int i=1;i<=n;i++)a[i]=fread();
	for(int i=1;i<=n;i++)ans+=find(i,m);
	fwrite(ans);
	return 0;
}