poj 3134 Power Calculus(IDA*)
2024-10-12 03:43:08
题目大意:
用最小的步数算出 x^n
思路:
直接枚举有限步数可以出现的所有情况。
然后加一个A* 就是如果这个数一直平方 所需要的步骤数都不能达到最优 就剪掉
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std; int n;
int save[1005]={1};
int h(int val)
{
if(val==0)return 0x3f3f3f3f; int cnt=0;
while(val<n)
{
val*=2;
cnt++;
}
return cnt;
}
bool dfs(int dep,int lit,int top)
{
if(dep>lit)return false; for(int i=0;i<top;i++)
{
save[top]=save[top-1]+save[i]; if(save[top]==n)return true;
if(dep+h(save[top])>lit)continue;
if(dfs(dep+1,lit,top+1))return true; save[top]=abs(save[top-1]-save[i]);
if(save[top]==n)return true;
if(dep+h(save[top])>lit)continue;
if(dfs(dep+1,lit,top+1))return true;
}
return false;
}
int main()
{
while(scanf("%d",&n)!=EOF && n)
{
save[0]=1;
if(n==1)printf("0\n");
else
for(int lit=1;;lit++)
{
if(dfs(1,lit,1))
{
printf("%d\n",lit);
break;
}
}
}
return 0;
}
最新文章
- MongoDB【第一篇】MongodDB初识
- Codeforces Round #342 (Div. 2) B. War of the Corporations(贪心)
- osgi dm
- 本人经过测试认为最简单最好的popupwindow样式
- 用c#开发微信 (13) 微统计 - 阅读分享统计系统 3 UI设计及后台处理
- (*p)++和*(p++)和*p++的区别
- Hadoop MapReduceV2(Yarn) 框架简介[转]
- photosop快速对白色背景图片进行抠图
- ASCII 码表对照
- mongodb中分页显示数据集的学习
- AospExtended K3 Note最新官方版 Android7.1.2 极速 省电 流畅 Galaxy XIAOMI Moto Lenovo Coolpad 均支持
- Node做中转服务器,转发接口
- 基于Python的数据分析(3):文件和时间
- 转:图像处理、显示中的行宽(linesize)、步长(stride)、间距(pitch)
- Python基础04_str_方法
- Python 3.4:Chromedrive,IEDriverServer,geckoDriver
- animate is not a function(zepto 使用报错)[转]
- sublime text 3中文乱码问题解决的方法
- HDU 1358 Period 求前缀长度和出现次数(KMP的next数组的使用)
- 用Docker自动构建纸壳CMS