华师一附中OI组

标题: P1164 小A点菜 [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-7-16 21:16
标题: 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






作者: 倚窗倾听风吹雨    时间: 2018-7-16 21:19
  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    时间: 2018-7-17 10:28
谢谢闻同学把题目贴上来，自己的解法也共享出来，大家向闻同学学习！
作者: 吴语林    时间: 2018-7-29 19:46
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2