自学内容网 自学内容网

【16届蓝桥杯寒假刷题营】第2期DAY2

1.快快变大 - 蓝桥云课

问题描述

小蓝非常喜欢数字,特别是大的数,但是对于超过一定界限的数,小蓝则会非常讨厌他,现在给定你 n 个数,以及一个上界 k,定义小蓝的喜爱值为选出的所有数的和,求小蓝的最大喜爱值为多少?

输入格式

第一行给定两个整数 n,k 表示共有 n 个数字以及上界 k。

第二行给定 n 个数,表示数的大小。

输出格式

输出一个整数表示小蓝的最大喜爱值。

输入案例

5 10
1 2 3 4 5

样例输出

16

评测数据规模

对于 100% 的评测数据:1≤n≤44,0≤k≤1e9。

思路:
 

代码如下:
爆搜:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,k;
const ll N = 1e3+10;
ll arr[N];
ll ans = -1e9;
void dfs(ll x, ll sum)
{
if(sum > k)
return;
if(x > n)
{
if(sum <= k)
{
ans = max(ans,sum);
}
return;
}
dfs(x+1,sum+arr[x]);
dfs(x+1,sum);
}
int main(void)
{
cin >> n >> k;
for(ll i = 1 ; i <= n ; i++)
cin >> arr[i];
 dfs(1,0);
cout << ans;
return 0;
}

二分:
 


原文地址:https://blog.csdn.net/zqystca/article/details/145429590

免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!