解题报告 P1164 小 A 点菜

题目内容

P1164

一个餐馆，n 种菜，每种菜只有一份，价值为 a_i 元，求刚好花完 m 元的方案总数。

解题思路

具体的思路就是，可以通过前面一个状态转移

令 f(i,x) 表示选了前 i 个物品后当前钱为 x 的方案个数，则有状态转移方程

f(i,x)=f(i-1,x)+f(i-1,x-a_i)

就是当前状态的方案数，可以选，可以不选，假设不选，那就有 f(i-1,x) 个方案，如果要选，那就有 f(i-1,x-a_i) 个方案，只需要两个方案数加起来即可，初始值 f(0,0) 设为 1 即可，然后第一维是可以滚动掉的，所以最终的转移方程是 f[j]+=f[j-a[i]]

#include <cstdio>

int n,m,a[105],f[10005];

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]];//进行递推
    printf("%d\n",f[m]);//输出最终结果
    return 0;
}