<—点个赞吧QwQ
宣传一下算法提高课整理
达达帮翰翰给女生送礼物,翰翰一共准备了 $N$ 个礼物,其中第 $i$ 个礼物的重量是 $G\[i\]$。
达达的力气很大,他一次可以搬动重量之和不超过 $W$ 的任意多个物品。
达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数,分别代表 $W$ 和 $N$。
以后 $N$ 行,每行一个正整数表示 $G\[i\]$。
输出格式
仅一个整数,表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围
$1 \\le N \\le 46$,
$1 \\le W,G\[i\] \\le 2^{31}-1$
输入样例:
20 5
7
5
4
18
1
输出样例:
19
思路
很明显,$\text{DFS}$ 时间复杂度是 $O(2^{46})$ ,会超时,考虑双向 $\text{DFS}$。
我们可以把数据砍成两段,一段长 $x$,另一端长 $n-x$,我们先把第一段的所有重量组合求出,也就是说求出所有第一次搜索能组成的重量。然后再第二次搜索时把搜索的答案和第一次搜索的答案进行组合,由于我们要最大,所以我们可以把第一次搜索能组成的所有进行排序,然后进行二分查找即可。
时间复杂度
第一次搜索时间复杂度 $O(2^x)$,第二次搜索时间复杂度 $O(2^{n-x}\log 2^x)$,总时间复杂度 $O(2^x + 2^{n-x}\log 2^x)$,由于第二次搜索时间复杂度较高,所以 $x$ 可以取 $\dfrac{n}{2}+1$,要注意下边界问题,但是 $x$ 取 $\dfrac{n}{2}$ 也能过。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 50;
int n,m,k;
LL a[N];
LL weight[1 << 24],cnt;
LL ans;
void dfs1 (int u,LL sum) {
if (u > k) {
weight[++cnt] = sum;
return ;
}
dfs1 (u + 1,sum);
if (sum + a[u] <= m) dfs1 (u + 1,sum + a[u]);
}
void dfs2 (int u,LL sum) {
if (u > n) {
int l = 1,r = cnt;
while (l < r) {
int mid = l + r + 1 >> 1;
if (weight[mid] + sum <= m) l = mid;
else r = mid - 1;
}
ans = max (ans,weight[l] + sum);
return ;
}
dfs2 (u + 1,sum);
if (sum + a[u] <= m) dfs2 (u + 1,sum + a[u]);
}
int main () {
cin >> m >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
sort (a + 1,a + 1 + n,greater <int> ());
k = n / 2;
dfs1 (1,0);
sort (weight + 1,weight + 1 + cnt);
cnt = unique (weight + 1,weight + 1 + cnt) - weight - 1;
dfs2 (k + 1,0);
cout << ans << endl;
return 0;
}
$tql$
orz , 终于看到一个跟我同一种码风的题解了
k = n / 2+1;或者说k=min(n,n/2+1)为什么都过不了了
n==1的时候
n=1的那个点是可以过的 但其他又有点过不了
那么k=n时,k+1>n了啊
3q
为啥超时
hack麻烦发一下
最后一组数据超时了 加个o2优化过了