P1164 小 A 点菜（动态规划）

题目背景uim 神犇拿到了 uoi 的 ra镭牌后立刻拉着基友小 A 到了一家……餐馆很低端的那种。uim 指着墙上的价目表太低级了没有菜单说“随便点”。题目描述不过 uim 由于买了一些书口袋里只剩 M 元 (0M≤10000)。餐馆虽低端但是菜品种类不少有 N 种 (1≤N≤100)第 i 种卖 ai​ 元 (0ai​≤1000)。由于是很低端的餐馆所以每种菜只有一份。小 A 奉行“不把钱吃光不罢休”的原则所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。由于小 A 肚子太饿所以最多只能等待 1 秒。输入格式第一行两个整数 N 和 M分别表示菜品种类和 uim 身上的钱数。第二行 N 个正整数 ai​可能有重复用空格隔开分别表示每种菜的价格。输出格式一个正整数表示点菜方案数保证答案的范围在 [0,231−1] 之内不超过 C/C 的int范围。输入输出样例输入 #1复制4 4 1 1 2 2输出 #1复制3说明/提示2020.8.29增添一组 hack 数据 by yummy代码#includebits/stdc.h using namespace std; int dp[101][10001]; int a[101],n,m; int main(){ cinnm; for(int i1;in;i){ cina[i]; } for(int i1;in;i){ for(int j1;jm;j){ dp[i][j]dp[i-1][j]; if(ja[i]){ dp[i][j]; } else if(ja[i]){ dp[i][j]dp[i-1][j-a[i]]; } } } coutdp[n][m]; return 0; }