此题妙矣
查看原帖
此题妙矣
471767
Ar_cher楼主2023/5/5 22:56

屑标题

60pts,T了4个点:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e8+100005;
int n,c,ans;
int fa[N];
void dfs(int x,int y){
	ans=max(y,ans);
	for(int i=1+x;i<=n;i++){
		if(y+fa[i]<=c) dfs(i,fa[i]+y);
	}
}
//最优性剪枝,某些状态把后面的砝码都选了最后也不能更新答案
signed main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>fa[i];
	}
	dfs(0,0);
	cout<<ans;
	return 0;
}
/*
这是未过的样例:
36 968459818
21
51
104
163
301
482
788
1297
2123
3447
5574
9028
14606
23669
38309
61980
100299
162307
262636
424976
687619
1112634
1800259
2912907
4713201
7626142
12339362
19965513
32304910
52270456
84575394
136845869
221421265
358267166
579688458
937955633
*/
2023/5/5 22:56
加载中...