点菜方案数

题目描述

不过uim的口袋里只剩 M元(M <= 10000)，来到了一家低端餐馆前。

餐馆虽低端，但是菜品种类不少，有 N 种(N <= 100)，第i种卖元(ai <= 1000)。由于是很低端的餐馆所以每种菜只有一份。

uim奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim 身上所有钱花完。他想知道有多少种点菜方法。由于小A 肚子太饿，所以最多只能等待 1秒

输入格式

第一行是两个数字，表示N和M

第二行起V 个正数 ai(可以有相同的数字，每个数字均在 1000 以内)。

输出格式

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

思路

我们用dp[n]表示花光n元钱的方案数，那么有下式：

于是dp[N]就是我们需要的答案。需要注意的是，初始化的时候，dp[0]=1，同时为了加速在计算dp[n]时i的枚举，我们可以将{ai}排序。

#include<iostream> 
#include<algorithm>
using namespace std;

const int maxm = 1e4;
const int maxn = 1e2;
int dp[maxm + 5], cost[maxn + 5];

int main(){
	int N, M, i, j;
	cin >> N >> M;
	for(i = 0; i < N; ++ i){
		cin >> cost[i];
	}
	sort(cost, cost + N);
	dp[0] = 1;
	for(j = cost[0]; j <= M; ++ j){
		for(i = 0; i < N && j >= cost[i]; ++ i){
			dp[j] += dp[j - cost[i]];
		}
	}
	cout << dp[M];
}