1 solutions
-
0
这题是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