折半搜索
折半一般可以把时间复杂度从 \(O(2^{n})\) 变成 \(O(2^{n/2} \cdot n)\)。
一般可以从初始状态搜一次, 从目标状态搜一次。
伪代码
void dfs1(int x, /*其他的状态*/){
if(x == mid + 1){
/*
统计发案数
*/
}
dfs1(x + 1, /*选第 x 个东西的代价*/);
dfs1(x + 1, /*不选第 x 个东西的代价*/);
}
void dfs2(int x, /*其他的状态*/){
if(x == mid){
/*
统计发案数
*/
}
dfs2(x - 1, /*选第 x 个东西的代价*/);
dfs2(x - 1, /*不选第 x 个东西的代价*/);
}
dfs1(1, /*...*/);
dfs2(n, /*...*/);
标签:折半,int,dfs2,dfs1,搜索,发案,代价
From: https://www.cnblogs.com/liuyichen0401/p/18138796