3. 椎名真白的午饭
题目ID:15698必做题100分
最新提交:Wrong Answer 10 分
历史最高:Wrong Answer 20 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
椎名真白每天的午饭一直是各种各样的年轮面包。
她掏出了n个年轮面包,第i个年轮面包含有的热量为w[i]。她可以选择吃掉其中一些,获得热量之和。
虽然椎名真白平时埋头画画对生活细节很不上心,但是对于自己的外貌身材还是十分在意的,她不想变得太胖或者太瘦,所以选择了一个热量获得区间[l,r],每天中午从年轮面包获得热量必须在该区间内。
显然有多种选择方案能够满足条件,但是真白是个数学白痴,她想让你帮忙计算一下所有方案数。
输入格式
第一行输入
3个正整数n,l,r(n≤40,1≤l≤r≤300)。
第二行输入n个正整数,表示每份年轮面包含有的热量wi。
输出格式
一行一个整数,表示所有方案数。
样例
Input 1
4 70 85
80 75 90 70
Output 1
3
样例解释
对于样例输入,有以下3种方案:
只吃第1个面包
只吃第2个面包
吃第4个面包
每一种方案的热量之和都在70到85的范围内。
数据范围
n≤40,1≤l≤r≤300,20≤w i≤100
我的代码:
#include <bits/stdc++.h>
using namespace std;
int n,l,r;
int dp[50][5000];
int main() {
cin >> n >> l >> r;
int w[105];
for(int i = 1 ; i <= n ; i++) {
cin >> w[i];
}
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i++) {
for(int j = r ; j >= w[i] ; j--) {
dp[i][j] = dp[i - 1][j];
if(dp[i][j] > 0){
dp[i][j] = dp[i - 1][j - w[i]] + dp[i - 1][j];
}
}
}
int sum = 0;
for(int j = l ; j <= r ; j++) {
sum += dp[n][j];
}
cout << sum << endl;
return 0;
}
这里有点问题,有大佬帮忙调一下吗
dp[i][j] = dp[i - 1][j];
(dp[i][j] > 0){
dp[i][j] = dp[i - 1][j - w[i]] + dp[i - 1][j];
}