思路构建

很容易想到用 $dp[i][j]$ 来代表从第 $1$ 个吃到第 $i$ 个时，能量和为 $j$ 的方案总数

转移方程式为: $dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]]$ (当 $j >= w[i]$ 时加第 2 项)

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,l,r,w[45],dp[45][305],s;
int main(){
	cin>>n>>l>>r;
	for(int i=1;i<=n;++i){
		cin>>w[i];
	}
	dp[0][0]=1;//初始化
	for(int i=1;i<=n;++i){
		for(int j=0;j<=300;++j){
			if(j>=w[i]){//判断
				dp[i][j]+=dp[i-1][j-w[i]];
			}
			dp[i][j]+=dp[i-1][j];
		}
	}
	for(int j=l;j<=r;++j){
		s+=dp[n][j];//加起来
	}
	cout<<s;
  return 0;//完美结束
}

空间压缩

可以将 $dp[i][j]$ 压缩成 $dp[j]$ ,但要注意,for循环要从大到小:

#include<bits/stdc++.h>
using namespace std;
int n,l,r,w[45],dp[305],s;
int main(){
	cin>>n>>l>>r;
	for(int i=1;i<=n;++i){
		cin>>w[i];
	}
	dp[0]=1;
	for(int i=1;i<=n;++i){
		for(int j=300;j>=w[i];--j){
			dp[j]+=dp[j-w[i]];
		}
	}
	for(int j=l;j<=r;++j){
		s+=dp[j];
	}
	cout<<s;
  return 0;
}