Programming Contest
题目链接:F - Programming Contest (atcoder.jp)
题目大意
用T分钟的时间去解决N道题,每道题需要相应的时间。可以选择其中的任意道,使剩下的时间最少。
解题思路
最容易想到的就是递归遍历所有的可能,然后取满足条件的最大值。然而N最大为40,每个题都有选和不选两种情况,这样最大时间复杂度为(O(2^{40})),肯定超时。
所以我们得采用trick优化。
我们将n个数两等分,然后分别枚举两部分的所有情况,并将结果保存在数组中,这样最大时间复杂度为(O(2*2^{20}))。然后我们再将得到的两个数组v1,v2升序排序,从v1和v2中各取一个数,求组成的最大的不超过T的数就行。对v1中的每一个数,我们可以直接二分v2寻找最佳匹配,此过程最大时间复杂度为(O(2^{20}log2^{20}))。
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, t, a[44];
vector<ll> v1, v2;
ll ans;
void dfs(int i, int e, ll sum, vector<ll>& v){
if(i==e){
if(sum<=t) {
ans = max(ans, sum);
v.push_back(sum);
}
return;
}
dfs(i+1, e, sum, v);
if(sum+a[i] <= t) dfs(i+1, e, sum+a[i], v);
}
int main(void)
{
cin>>n>>t;
for(int i=0;i<n;++i) cin>>a[i];
dfs(0, n/2, 0, v1);
dfs(n/2, n, 0, v2);
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int num1 = v1.size();
for(int i=0;i<num1;++i){
int p = upper_bound(v2.begin(), v2.end(), t-v1[i]) - v2.begin();
ans = max(ans, v1[i]+v2[p-1]);
}
cout<<ans;
return 0;
}