题目内容

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;
}
最后修改日期:2020年2月27日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。