題目描述

uim神犇拿到了uoi的ra（鐳牌）后，立刻拉著基友小A到了一家……餐館，很低端的那種。

uim指著墻上的價目表（太低級了沒有菜單），說：“隨便點”。

不過uim由于買了一些輔（e）輔（ro）書，口袋里只剩?M?元 (M≤10000)?。

餐館雖低端，但是菜品種類不少，有?N?種 (N≤100)?，第?i?種賣?ai??元?((ai?≤1000)?。由于是很低端的餐館，所以每種菜只有一份。

小A奉行“不把錢吃光不罷休”，所以他點單一定剛好吧uim身上所有錢花完。他想知道有多少種點菜方法。

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

輸入輸出格式

輸入格式：

第一行是兩個數(shù)字，表示?N?和?M?。

第二行起?NN?個正數(shù)?ai??（可以有相同的數(shù)字，每個數(shù)字均在?1000?以內(nèi)）。

輸出格式：

一個正整數(shù)，表示點菜方案數(shù)，保證答案的范圍在?int?之內(nèi)。

輸入輸出樣例

輸入樣例#1：

4 4
1 1 2 2

輸出樣例#1：

3

思路：01背包模板

源代碼

#include<iostream> using namespace std; int main() {int money,num;int price[1000],plan[10000]={0};int i,j;cin>>num>>money;for(i=1;i<=num;i++) cin>>price[i];//輸入菜品價格plan[0]=1;//至少有一種方案for(i=1;i<=num;i++)//每種菜依次進(jìn)行比較{for(j=money;j>=price[i];j--)//從現(xiàn)有錢數(shù)開始，直至當(dāng)前菜為止{plan[j]=plan[j]+plan[j-price[i]];//當(dāng)前的花費=之前的花費+不點這個菜的花費}}cout<<plan[money]<<endl;//輸出最后一次的花費return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的小A点菜（洛谷-P1164）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。