P1164 小A点菜

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1164

这道题题目有毒复制过来是一堆乱码。。到洛谷上去看吧。
题目背景
uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。

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

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

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

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

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

输入输出格式
输入格式：
第一行是两个数字，表示 N 和 M 。

第二行起 N 个正数 ai（可以有相同的数字，每个数字均在 1000 以内）。

输出格式：
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

输入输出样例
输入样例#1：
4 4
1 1 2 2
输出样例#1：
3

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int m,n,a[200],f[200][10010];
   
4. int i,j;
   
5. int main()
   
6. {
   
7.     cin>>n>>m;
   
8.     for(i=1;i<=n;i++)
   
9.         cin>>a[i];
   
10.     for(i=1;i<=n;i++)
    
11.     {
    
12.         for(j=1;j<=m;j++)
    
13.         {
    
14.             if(j<a[i])f[i][j]=f[i-1][j];
    
15.             if(j>a[i])f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
    
16.             if(j==a[i])f[i][j]=f[i-1][j]+1;
    
17.         }
    
18.     }
    
19.     cout<<f[n][m];
    
20. }

复制代码

admin

谢谢闻同学把题目贴上来，自己的解法也共享出来，大家向闻同学学习！

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,m,v[110],f[1010]={0};
    
14. int main()
    
15. {
    
16.     scanf("%d%d",&n,&m);
    
17.     for(int i=1;i<=n;i++)
    
18.             scanf("%d",&v[i]);
    
19.     f[0]=1;
    
20.     for(int i=1;i<=n;i++)
    
21.             for(int j=m;j>=v[i];j--)
    
22.                     f[j]+=f[j-v[i]];
    
23.     printf("%d",f[m]);
    
24.     return 0;
    
25. }

复制代码