點菜方案數

題目描述

不過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];
}