1 solutions

  • 0
    @ 2021-10-12 16:58:41

    这题是01背包的变形。大家在学习完01背包后就可以试试了。 要注意的是本题是统计方案数, 要处理好边界,即f[0]=1,因为一开始就是从1进行遍历的,不管有几种菜,他必须有一种点菜的方法。 上代码

    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int N,M;
    int a[101];
    int f[10001];
    int main()
    {
    	scanf("%d%d",&M,&N);
    	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",f[M]);
    	return 0;
    }
    
    
    • 1

    Information

    ID
    14
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    2
    Accepted
    2
    Uploaded By