网站推广引流软件,常州网站制作维护,南京鼓楼做网站公司,免费h5页面制作工具小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra#xff08;镭牌#xff09;后#xff0c;立刻拉着基友小 A 到了一家……餐馆#xff0c;很低端的那种。
uim 指着墙上的价目表#xff08;太低级了没有菜单#xff09;#xff0c;说#xff1a;“随便点”。
题目描述
…小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra镭牌后立刻拉着基友小 A 到了一家……餐馆很低端的那种。
uim 指着墙上的价目表太低级了没有菜单说“随便点”。
题目描述
不过 uim 由于买了一些书口袋里只剩 M M M 元 ( M ≤ 10000 ) (M \le 10000) (M≤10000)。
餐馆虽低端但是菜品种类不少有 N N N 种 ( N ≤ 100 ) (N \le 100) (N≤100)第 i i i 种卖 a i a_i ai 元 ( a i ≤ 1000 ) (a_i \le 1000) (ai≤1000)。由于是很低端的餐馆所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿所以最多只能等待 1 1 1 秒。
输入格式
第一行是两个数字表示 N N N 和 M M M。
第二行起 N N N 个正数 a i a_i ai可以有相同的数字每个数字均在 1000 1000 1000 以内。
输出格式
一个正整数表示点菜方案数保证答案的范围在 int 之内。
样例 #1
样例输入 #1
4 4
1 1 2 2样例输出 #1
3提示
2020.8.29增添一组 hack 数据 by yummy
#include iostream
using namespace std;
#define N 101int n,m,a[N],f[N][10001];//f数组保存方法总数量int main() {cin nm;//n代表菜的数量m代表当前有多少钱for (int i 1; i n; i) cin a[i];//输入每种菜的价格//当前第i种物品恰好为j元钱所以可以只买它自己。//这种情况其实包含在1中但是由于f[i][0]0所以不会算入这种情况。//所以我们要把所有的f[i][0]更新成1这样就可以计算上面所述的那种情况//i代表哪个菜0可以理解为你的钱和当前菜品的价格一样两者做了减法如同j - a[i]for (int i 0; i n; i) f[i][0] 1; // 初始化第一列全部为1for (int i 1; i n; i){for (int j 1; j m; j) {//不买当前第i道菜品这时候也就是前i-1个物品凑成j的方案即f[i][j]f[i-1][j]f[i][j] f[i - 1][j];//买当前第i道菜品这个时候前i-1个物品所需要的钱应该是j-a[i],//也就是说前i个物品中所有能凑出j-a[i]元的方案再加上当前这道菜品//就可以变成前i个物品所需的钱为j的方案数。//即f[i][j]f[i-1][j-a[i]]if (j a[i]) f[i][j] f[i - 1][j - a[i]]; cout f[i][j] ;//输出当前i个物品凑成j元的方案数}cout endl;}cout f[n][m] endl;return 0; // 程序执行成功返回0
}这个题目我在做的时候我发现这个题目重在策划策划一个问题的解决思路纯纯的逻辑思维反而有点加大难度。
