P10484 送礼物_牛客博客

拿到这道题，很容易写一个 $\mathcal {O}(2^n)$ 的算法，可是注意 $n<=46$ ,必通不过此题。但是如果能减少一半的搜索树规模，是能在 $2s$ 内通过 $\frac{n}{2}$ 规模的测试样例的，于是我们就想到了双向搜索，具体的做法是：先搜索 $[1,n/2+2]$ ,然后将所有可能的重量存入数组，排序之后再搜索 $[n/2+3,n]$ ,这样的话对于第二趟搜索得到的每一个重量 $curr$ ，我们去二分查找第一趟得到数组中不大于 $W-curr$ 的最大项，这部分可以用 $upper\_bound()$ 实现。为什么区间的 $mid$ 不是 $n/2$ 呢？答案是蓝书给的经验公式。一开始我使用了 $set$ 排序、去重，但是这有两个问题，一是递归树本身就包含了不选的决策，应该在最后一层递归再加入集合，而我在每一次递归都试图放进集合；二是 $set$ 是大常数数据结构，频繁的插入是程序的性能瓶颈，另外就是没开 $long\ long$ 。

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<algorithm>

int res;
int index;
std::set<int> s;
std::unordered_set<int> u_s;

void forward_DFS(const int& n,const std::vector<int>& v, const int& W,int& curr,int d)
{
	s.insert(curr);
	if (d == n + 1)
	{
		return;
	}
	if (curr + v[d] <= W)
	{
		curr += v[d];
		forward_DFS(n, v, W, curr, d + 1);
		curr -= v[d];
	}
	forward_DFS(n, v, W, curr, d + 1);
}

void backward_DFS(const int& n, const std::vector<int>& v, const int& W, int& curr, int d)
{
	if (!u_s.count(curr))
	{
		auto it = s.upper_bound(W - curr);
		if (it != s.begin())
		{
			it--;
			res = std::max(res, *it + curr);
		}
		u_s.insert(curr);
	}
	if (d == n + 1)
	{
		return;
	}
	if (curr + v[d] <= W)
	{
		curr += v[d];
		backward_DFS(n, v, W, curr, d + 1);
		curr -= v[d];
	}
	backward_DFS(n, v, W, curr, d + 1);
}

int main()
{
	int w, n;
	std::cin >> w >> n;
	std::vector<int> v(50);
	for (int i = 1; i <= n; i++)
	{
		std::cin >> v[i];
	}
	std::sort(v.begin() + 1, v.end(), std::greater<int>());
	int curr = 0;
	forward_DFS(n / 2 + 2	, v, w, curr, 1);
	backward_DFS(n, v, w, curr, n / 2 + 3);
	std::cout << res;
}

然后把用集合的地方换成 $vector$ 再排序,第二个递归的 $unordered\_set$ 去掉， $curr、res$ 改成 $long\ long$ ,即可通过此题。

第一次搜索的时间复杂度为

\mathcal O(2^{n/2})

产生的数组长度不会超过 $2^{n/2}$ ,那么排序的代价为

\mathcal O ({n/2\cdot log(2^{n/2}}))

第二次搜索会对递归树叶子进行二次查找，复杂度为

\mathcal O(2^{n/2}\cdot log(2^{n/2}))=\mathcal O(2^{n/2}\cdot n)

最后补一句，这道题去重不去重无所谓，反正我的代码前后只快了 $30ms$ 左右。

#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<algorithm>

long long res;
int index;
//std::set<int> s;
std::vector<int> s;
//std::unordered_set<int> u_s;

void forward_DFS(const int& n,const std::vector<int>& v, const int& W,long long& curr,int d)
{
	if (d == n + 1)
	{
		s.push_back(curr);
		return;
	}
	if (curr + v[d] <= W)
	{
		curr += v[d];
		forward_DFS(n, v, W, curr, d + 1);
		curr -= v[d];
	}
	forward_DFS(n, v, W, curr, d + 1);
}

void backward_DFS(const int& n, const std::vector<int>& v, const int& W, long long& curr, int d,const std::vector<int>::iterator end_it)
{
	if (d == n + 1)
	{
		auto it = std::upper_bound(s.begin(), end_it, W - curr);
		if (it != s.begin())
		{
			it--;
			res = std::max(res, *it + curr);
		}
		return;
	}
	if (curr + v[d] <= W)
	{
		curr += v[d];
		backward_DFS(n, v, W, curr, d + 1,end_it);
		curr -= v[d];
	}
	backward_DFS(n, v, W, curr, d + 1,end_it);
}

int main()
{
	int w, n;
	std::cin >> w >> n;
	std::vector<int> v(50);
	for (int i = 1; i <= n; i++)
	{
		std::cin >> v[i];
	}
	std::sort(v.begin() + 1, v.end(), std::greater<int>());
	long long curr = 0;
	forward_DFS(n / 2 + 2	, v, w, curr, 1);
	std::sort(s.begin(), s.end());
	auto end_it = std::unique(s.begin(), s.end());
	backward_DFS(n, v, w, curr, n / 2 + 3,end_it);
	std::cout << res;
}