首页 > 代码库 > UVa1374 Power Calculus (IDA*)
UVa1374 Power Calculus (IDA*)
链接：http://acm.hust.edu.cn/vjudge/problem/41552
分析：枚举最大深度maxd，每次总是使用“刚刚得到”的那个数（LRJ说的我信了），每次递归枚举a[d+1],两种方式a[d]+或-去a[i]，找到解返回true，否则直至枚举结束都没有找到解则返回false，dfs出口有四个，一是a[d]==n，说明最少用d次操作能得到目标，二是枚举完所有a[d+1]也没找到解，然后加上两个剪枝，深度大于等于最大深度还有乐观估计接下来maxd-d次每次都取指数最大相加但结果还是小于n都返回失败false。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std;dfs 4 5 int n, a[13]; 6 7 bool dfs(int d, int maxd) { 8 if (a[d] == n) { 9 printf("%d\n", d);10 return true;11 }12 if (d == maxd) return false;13 int maxv = a[0];14 for (int i = 1; i <= d; i++) maxv = max(maxv, a[i]);15 if ((maxv << (maxd - d)) < n) return false;16 for (int i = d; i >= 0; i--) {17 a[d + 1] = a[d] + a[i];18 if (dfs(d + 1, maxd)) return true;19 if (a[d] - a[i] <= 0) continue;20 a[d + 1] = a[d] - a[i];21 if (dfs(d + 1, maxd)) return true;22 }23 return false;24 }25 26 void solve() {27 if (n == 1) printf("%d\n", 0);28 else {29 a[0] = 1;30 for (int maxd = 1; ; maxd++)31 if (dfs(0, maxd)) break;32 }33 }34 35 int main() {36 while (scanf("%d", &n) == 1 && n > 0) solve();37 return 0;38 }
UVa1374 Power Calculus (IDA*)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。