P1220 关路灯 搜索剪枝

题目链接:
https://www.luogu.com.cn/problem/P1220
在搜索题单里第一次看到这种题目被吓住了
和之前我刷过的搜索题(全是板子)比,这里需要不断地朝不同方向搜索
并且让人汗流浃背的是1≤n≤50,爆搜肯定是炸了.
考虑这三个点
1.如何去遍历左右节点
2.记录状态的方案
3.怎么去优化节点搜索方案
1.遍历方法:
在每次搜索的时候选择左右两边遍历相邻顶点并且需要确保不越界

1. for(int i = 1;i<=n;++i){
2. //当前的位置
3. int _pos = (pos +- i);
4. //判断位置的合法性
5. _pos >= 1(向左)_pos <= n (向右)
6. //~~更新状态~~
7. }

复制代码

做到这里,你只能得40分,因为还有一个点没优化
在遍历的过程中一旦确定了节点就说明当前节点没有实际用处了.
所以在dfs还原现场后退出for循环就行了
AC代码
[code]#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[N],v[N];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[k] = 1;    dfs(k,1,0,sum - v[k],0);    cout