”从大到小“ 还是”从小到大“搜索比较好?
查看原帖
”从大到小“ 还是”从小到大“搜索比较好?
592223
Allorry楼主2023/11/4 17:44

求助大佬,如下代码是从大到小搜索,至少yxc是这么讲的:为了优化搜索顺序,要从分支小的地方开始。 他的代码也差不多是这么敲的,而且在acwing那边,从大到小的时间要好很多。 但这题偏偏反过来了,从小到大时间反而少很多

bool dfs(int u, int depth) {
    if (u > depth) return false;
    if (path[u - 1] == n) return true;
    if (path[u - 1] << (depth - u + 1) < n) return false;

    bool vis[N] = {};

    for (int i = u - 1; i >= 0; i--)
        for (int j = i; j >= 0; j--) {
            int s = path[i] + path[j];
            if (s > n || vis[s] || s <= path[u - 1]) continue;
            vis[s] = 1;
            path[u] = s;
            if (dfs(u + 1, depth)) return true;
        }
    return false;
}
2023/11/4 17:44
加载中...