洛谷P1164小A点菜（01背包）

题目背景

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

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

题目描述

不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩MMM元(M≤10000)(M \le 10000)(M≤10000)。

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

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

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

输入格式

第一行是两个数字，表示NNN和MMM。

第二行起NNN个正数aia_iai（可以有相同的数字，每个数字均在100010001000以内）。

输出格式

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

输入输出样例

输入 #1

4 4

1 1 2 2

输出 #1

3
这个题和蓝书上CH5201这道是一样的，都是魔改01背包问题而来。设dp[i,j]表示前i种菜选或者不选，凑出来j元的种类数，可以得到转移方程方程 dp[i,j]=dp[i-1,j]+dp[i-1,j-a[i]];和01背包不同，这里直接把这两个i-1阶段的值相加了，因为要求的是方案总数，选或者不选都有贡献。不要被 dp[j]+=dp[j-a[i]]这种写法迷惑，dp[j]=dp[j]+dp[j-a[i]]里右边两项都是上一个阶段的，左边一项是当前阶段的，满足线性dp的要求。要注意的是，存在一种情况是只买第i种菜凑成m元，这种情况决定了我们需要为dp[i][0]赋值为1，一维数组的话就是dp[0]=1，每每循环到j=a[i]
时，dp[0]=1就是剩余的钱刚好买完一个菜后用完，是可以用完的情况，所以要在一开始就赋值为1（循环里会用到它而不改变它的值），再次注意“dp[i,j]表示前i种菜选或者不选”，是前i种而不包括第i种，dp[i,0]代表前i种不选（没花钱）而选了价值为a[i]=m的第i种菜品导致直接凑够了钱数要求，这种方案数为1就很好理解了。

#include <bits/stdc++.h>

using namespace std;

int a[];

int dp[]={};

int main()

{

    int n,m;

    cin>>n>>m;

    int i,j;

    for(i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    dp[]=;

    for(i=;i<=n;i++)

    {

        for(j=m;j>=a[i];j--)

        {

            dp[j]+=dp[j-a[i]];//实际上转移方程是 dp[i,j]=dp[i-1,j]+dp[i-1,j-a[i]]; 不要被一维数组的写法搞晕

        }

    }

    cout<<dp[m];//要求恰好花掉m元

    return ;

}

巴特西