求助大佬,如下代码是从大到小搜索,至少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;
}