【洛谷 1164】小A點菜

題目背景

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

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

題目描述

不過uim由于買了一些輔（e）輔（ro）書，口袋裡隻剩MM元(M \le 10000)(M≤10000)。

餐館雖低端，但是菜品種類不少，有NN種(N \le 100)(N≤100)，第ii種賣a_ia

i

​     元(a_i \le 1000)(a

i

​     ≤1000)。由于是很低端的餐館，是以每種菜隻有一份。

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

由于小A肚子太餓，是以最多隻能等待11秒。

輸入輸出格式

輸入格式：

第一行是兩個數字，表示NN和MM。

第二行起NN個正數a_ia

i

​     （可以有相同的數字，每個數字均在10001000以内）。

輸出格式：

一個正整數，表示點菜方案數，保證答案的範圍在intint之内。

輸入輸出樣例

輸入樣例#1： 複制

4 4

1 1 2 2

輸出樣例#1： 複制

3

題解：來題水題壓壓驚。01背包就是選或者不選如果選目前的

第i道，那麼你要花的錢是a[i]，f[j]表示使得總花費為j的方案數，現在因為j可以通過選第i道菜得到j+a[i]的價錢，是以f[j+a[i]]的方案數就要加上f[j]。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long ll;
using namespace std;
int n,m,a[105],f[1005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            f[j]+=f[j-a[i]];
        }
    }
    cout<<f[m];
    return 0;
}      

轉載于:https://www.cnblogs.com/wuhu-JJJ/p/11139671.html