【dfs+剪枝+前缀和】【洛谷P5194】

传送门

#include
#include
#define int long long
using namespace std;
const int maxn=1010;
int nums[maxn],sum[maxn]={0},goal;
int ans=0;
void dfs(int now,int s)
{
	if(now==-1) return;//终止条件 
	if(sum[now]+s<=goal)//剪枝2
	{
		ans=max(ans,s+sum[now]);
		return ;
	}
	if(nums[now]+s<=goal)
	{
		ans=max(ans,nums[now]+s);
		dfs(now-1,nums[now]+s);
	}
	dfs(now-1,s);
}
signed main()
{
	int n,cot=0;
	cin>>n>>goal;
	for(int i=0;i>num;
		if(num<=goal)//剪枝1
			nums[cot++]=num;
	 } 
	sum[0]=nums[0];
	for(int i=1;i