2476: 【普及-】【P1164】小A点菜
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：7
解决：1
题目描述
不过 uim 由于买了一些书，口袋里只剩 元 。
餐馆虽低端，但是菜品种类不少，有 种 ，第 种卖 元 。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 秒。
输入
第一行是两个数字，表示 和 。
第二行起 个正数 （可以有相同的数字，每个数字均在 以内）。
输出
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
样例输入 复制
4 4
1 1 2 2样例输出 复制
3提示
#include<bits/stdc++.h>
using namespace std;
int n,m,a[110];
long long ans;
void sol(int sum,int startx) {
if (sum==m) {
ans++;
return;
}else if (sum>m) {
return;
}
for (int i=startx;i<n;i++) {
sol(sum+a[i],i+1);
}
}
bool cmp(int x,int y) {
return x>y;
}
int main(){
cin>>n>>m;
for (int i=0;i<n;i++) {
cin>>a[i];
}
sort(a,a+n,cmp);
sol(0,0);
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],f[105][10005] = {0};
int main(){
cin >> n >> m;
for(int i = 1; i <=n; i++) cin >>a[i];
for(int i = 1; i <=n; i++){
for(int j = 1;j <= m; j++){
if(a[i] == j){
f[i][j] = f[i-1][j] + 1;
}else if(a[i] > j){
f[i][j] = f[i-1][j];
}else{
f[i][j] = f[i-1][j] + f[i-1][j-a[i]];
}
}
}
cout << f[n][m];
return 0;
}