高端响应式网站建设,南通大型网站建设,男通网站哪个好用,华为开发者选项在哪里打开本题思路来源于acwing算法提高课
题目描述 看本文需要准备的知识
1.二分#xff08;强烈推荐文章#xff1a;一分钟学会二分模板
2.dfs基本思想#xff0c;了解“剪枝”这个术语
思路分析
首先这道题目看起来就是一个01背包#xff0c;但是如果直接用01背包去做…本题思路来源于acwing算法提高课
题目描述 看本文需要准备的知识
1.二分强烈推荐文章一分钟学会二分模板
2.dfs基本思想了解“剪枝”这个术语
思路分析
首先这道题目看起来就是一个01背包但是如果直接用01背包去做时间复杂度为2^31*46一定会超时如果直接使用爆搜也一定会超时爆栈此时我们对爆搜进行优化采用双向dfs去搞定这个题目
整体思路是下面的两步
step one使用爆搜对前N/2个礼物打表下面会说这里的打表具体指什么需要的时间复杂度是2^(N/2)
step two对剩下的N/2个礼物进行爆搜对搜索树最后一层的每个结点的“礼物重量和”s使用二分从前N/2个礼物的打表中找到最大不超过w-s的值w是能拿的礼物重量的上限求所有这些值的最大值ans
第一个问题step one中的打表是什么比如有三个礼物重量分别为1,2,3可以打表的个数为2^3个分别是0,1,2,3,3,4,5,6其实就是所有礼物的重量组合很明显打表之后会出现重量重复的情况所以可以通过去重做一个小优化此处去重是使用头文件algorithm中的unique函数假设打表后的数组为weight,元素总个数为cnt则可以写排序之后再用
cntunique(weight,weightcnt)-weight;
第二个问题step two中“搜索树最后一层的每个结点的礼物重量和”是什么意思其实这个跟对前N/2个礼物打表是完全等价的只不过是对后N/2个礼物进行打表并且这个结果没有记录下来而是当场直接使用了而已具体的意思可以看代码理解
最后还可以做一个小优化就是把刚开始的重量数组g[46]从大到小排序这实际上是优化搜索顺序减少递归树的分支
完整代码
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N50;
typedef long long LL;
int g[N];
int weight[125],cnt;
int n,w,k;
int ans0;
void dfs1(int u,int s)
{if(uk){//coutu sendl;weight[cnt]s;return;}dfs1(u1,s);if((LL)sg[u]w)dfs1(u1,sg[u]);
}
void dfs2(int u,int s)
{if(un){int l-1,rcnt;while(l1!r){int mid(lr)/2;if(weight[mid]w-s)lmid;else rmid;}//coutweight[l]sendl;if (weight[l](LL)sw)ansmax(ans,weight[l]s);return;}dfs2(u1,s);if((LL)sg[u]w)dfs2(u1,sg[u]);
}
int main()
{cinwn;for(int i0;in;i)cing[i];sort(g,gn);reverse(g,gn);kn/2; dfs1(0,0);sort(weight,weightcnt);// for(int i0;icnt;i)coutweight[i]endl;cntunique(weight,weightcnt)-weight;// for(int i0;icnt;i)coutweight[i]endl;dfs2(k,0);coutansendl;return 0;
}
