思路构建

很容易想到用 $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;
}

#2742. 规划食谱题解#

本题考查搜索，乍一看貌似不怎么难，但我在做题时也不是一帆风顺。

常见问题1：数据重复。

一测样例，完了，数字超大，当然，函数是关键，弄好了就不会这样了。 我的代码（函数部分）：

void f(int h,int j){
	if(h>=b){
		g++;
	}
	for(int i=j;i<=a;i++){
		if(h+d[i]<=c&&e[i]==0){
			e[i]=1;
			f(h+d[i],i+1);
			e[i]=0;
		}
	}
}

常见问题2：数组大小。

好不容易把函数弄好了，结果还是90分，原来数组定义也要小心！！！ 我的代码（定义部分）：

int a,b,c,d[41],e[41],g;

完整代码：

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d[41],e[41],g;
void f(int h,int j){
	if(h>=b){
		g++;
	}
	for(int i=j;i<=a;i++){
		if(h+d[i]<=c&&e[i]==0){
			e[i]=1;
			f(h+d[i],i+1);
			e[i]=0;
		}
	}
}
int main(){
	cin>>a>>b>>c;
	for(int i=1;i<=a;i++){
		cin>>d[i];
	}
	f(0,1);
	cout<<g;
	return 0;
}

喜欢的点个赞！