P1220 关路灯 搜索剪枝
题目链接:https://www.luogu.com.cn/problem/P1220
在搜索题单里第一次看到这种题目被吓住了
和之前我刷过的搜索题(全是板子)比,这里需要不断地朝不同方向搜索
并且让人汗流浃背的是1≤n≤50,爆搜肯定是炸了.
考虑这三个点
1.如何去遍历左右节点
2.记录状态的方案
3.怎么去优化节点搜索方案
1.遍历方法:
在每次搜索的时候选择左右两边遍历相邻顶点并且需要确保不越界
for(int i = 1;i<=n;++i){
//当前的位置
int _pos = (pos +- i);
//判断位置的合法性
_pos >= 1(向左)_pos <= n (向右)
//~~更新状态~~
}做到这里,你只能得40分,因为还有一个点没优化
在遍历的过程中一旦确定了节点就说明当前节点没有实际用处了.
所以在dfs还原现场后退出for循环就行了
AC代码
#includeusing namespace std;using ll = long long;const int inf = INT_MAX;const int N = 55;int T;int n,k;int ans = inf;int a,v;bitsetvis;int sum = 0;//现在的端点,关掉的灯的总数,走路时间,剩余的功率,耗电量void dfs(int pos,int closed,int _time,int cost,int _sum){ if(_sum + cost * _time >= ans)return; if(closed == n){ ans = min(ans,_sum); return; } for(int i = 1;in>>k; for(int i = 1;i>a>>v; sum += v; } vis = 1; dfs(k,1,0,sum - v,0); cout 过来提前占个楼 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 东西不错很实用谢谢分享 感谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享 yyds。多谢分享 感谢，下载保存了 鼓励转贴优秀软件安全工具和文档！ 收藏一下 不知道什么时候能用到 谢谢楼主提供！ 懂技术并乐意极积无私分享的人越来越少。珍惜 分享、互助 让互联网精神温暖你我 感谢，下载保存了 分享、互助 让互联网精神温暖你我 鼓励转贴优秀软件安全工具和文档！ 用心讨论，共获提升！ 这个有用。 这个好，看起来很实用
页:
[1]
2