题目P1164 小 A 点菜题目背景uim 神犇拿到了 uoi 的 ra镭牌后立刻拉着基友小 A 到了一家……餐馆很低端的那种。uim 指着墙上的价目表太低级了没有菜单说“随便点”。题目描述不过 uim 由于买了一些书口袋里只剩M MM元( 0 M ≤ 10000 ) (0 M \le 10000)(0M≤10000)。餐馆虽低端但是菜品种类不少有N NN种( 1 ≤ N ≤ 100 ) (1 \le N \le 100)(1≤N≤100)第i ii种卖a i a_iai元( 0 a i ≤ 1000 ) (0 a_i \le 1000)(0ai≤1000)。由于是很低端的餐馆所以每种菜只有一份。小 A 奉行“不把钱吃光不罢休”的原则所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。由于小 A 肚子太饿所以最多只能等待1 11秒。输入格式第一行两个整数N NN和M MM分别表示菜品种类和 uim 身上的钱数。第二行N NN个正整数a i a_iai可能有重复用空格隔开分别表示每种菜的价格。输出格式一个正整数表示点菜方案数保证答案的范围在[ 0 , 2 31 − 1 ] [0,2^{31}-1][0,231−1]之内不超过 C/C 的int范围。输入输出样例 #1输入 #14 4 1 1 2 2输出 #13说明/提示2020.8.29增添一组 hack 数据 by yummy代码1二维数组#includebits/stdc.husingnamespacestd;constintN10010,M1000010;intn,V,v,f[N][M];intmain(){cinnV;f[0][0]1;for(inti1;in;i){cinv;for(intj0;jV;j){f[i][j]f[i-1][j];if(vj)f[i][j]f[i-1][j-v];}}coutf[n][V];return0;}代码2一维数组#includebits/stdc.husingnamespacestd;constintM1000010;intn,V,v,f[M];intmain(){cinnV;f[0]1;for(inti1;in;i){cinv;for(intjV;jv;j--)f[j]f[j-v];}coutf[V];return0;}结果
题目P1164 小 A 点菜题目背景uim 神犇拿到了 uoi 的 ra镭牌后立刻拉着基友小 A 到了一家……餐馆很低端的那种。uim 指着墙上的价目表太低级了没有菜单说“随便点”。题目描述不过 uim 由于买了一些书口袋里只剩M MM元( 0 M ≤ 10000 ) (0 M \le 10000)(0M≤10000)。餐馆虽低端但是菜品种类不少有N NN种( 1 ≤ N ≤ 100 ) (1 \le N \le 100)(1≤N≤100)第i ii种卖a i a_iai元( 0 a i ≤ 1000 ) (0 a_i \le 1000)(0ai≤1000)。由于是很低端的餐馆所以每种菜只有一份。小 A 奉行“不把钱吃光不罢休”的原则所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。由于小 A 肚子太饿所以最多只能等待1 11秒。输入格式第一行两个整数N NN和M MM分别表示菜品种类和 uim 身上的钱数。第二行N NN个正整数a i a_iai可能有重复用空格隔开分别表示每种菜的价格。输出格式一个正整数表示点菜方案数保证答案的范围在[ 0 , 2 31 − 1 ] [0,2^{31}-1][0,231−1]之内不超过 C/C 的int范围。输入输出样例 #1输入 #14 4 1 1 2 2输出 #13说明/提示2020.8.29增添一组 hack 数据 by yummy代码1二维数组#includebits/stdc.husingnamespacestd;constintN10010,M1000010;intn,V,v,f[N][M];intmain(){cinnV;f[0][0]1;for(inti1;in;i){cinv;for(intj0;jV;j){f[i][j]f[i-1][j];if(vj)f[i][j]f[i-1][j-v];}}coutf[n][V];return0;}代码2一维数组#includebits/stdc.husingnamespacestd;constintM1000010;intn,V,v,f[M];intmain(){cinnV;f[0]1;for(inti1;in;i){cinv;for(intjV;jv;j--)f[j]f[j-v];}coutf[V];return0;}结果
