【IDA*】POJ3134[Power Calculus]题解

题目概述

刚开始你知道x，用最少次数的乘除得到 xn 。

解题报告

因为乘除会用到之前求出的数据，所以这道题并不能用正常的BFS或DP解决，而普通DFS这道题不适用，因为深度可能比较大，会很慢。然后我就想到了IDDFS，结果还是很慢，样例都跑不出来……最后想到IDA*，其实就是在IDDFS中加了一个估价函数（好像就是剪枝），如果当前的指数now不停扩倍变成$now<&#xff08;ans表示IDA*当前枚举的答案&#xff0c;dep表示当前的深度&#xff09;都没有达到n&#xff0c;那么就可以剪掉了。</p> <h2 id="示例程序">示例程序</h2> <span class="hljs-preprocessor">#include&lt;cstdio&gt;</span> <span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxn&#61;<span class="hljs-number">1000</span>,maxp&#61;<span class="hljs-number">2048</span>; <span class="hljs-keyword">int</span> n,ans,now[maxn&#43;<span class="hljs-number">5</span>]; <span class="hljs-keyword">bool</span> IDAX(<span class="hljs-keyword">int</span> dep) { <span class="hljs-keyword">if</span> (dep&gt;ans) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">if</span> ((now[dep]&lt;&lt;ans-dep)&lt;n) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-comment">//剪枝</span> <span class="hljs-keyword">if</span> (now[dep]&#61;&#61;n) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i&#61;<span class="hljs-number">0</span>;i&lt;&#61;dep;i&#43;&#43;) { now[dep&#43;<span class="hljs-number">1</span>]&#61;now[dep]&#43;now[i];<span class="hljs-keyword">if</span> (IDAX(dep&#43;<span class="hljs-number">1</span>)) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; now[dep&#43;<span class="hljs-number">1</span>]&#61;now[dep]-now[i];<span class="hljs-keyword">if</span> (IDAX(dep&#43;<span class="hljs-number">1</span>)) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; } <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; } <span class="hljs-keyword">int</span> main() { freopen(<span class="hljs-string">&#34;program.in&#34;</span>,<span class="hljs-string">&#34;r&#34;</span>,stdin); freopen(<span class="hljs-string">&#34;program.out&#34;</span>,<span class="hljs-string">&#34;w&#34;</span>,stdout); now[<span class="hljs-number">0</span>]&#61;<span class="hljs-number">1</span>; <span class="hljs-keyword">for</span> (<span class="hljs-built_in">scanf</span>(<span class="hljs-string">&#34;%d&#34;</span>,&n);n;<span class="hljs-built_in">scanf</span>(<span class="hljs-string">&#34;%d&#34;</span>,&n)) { <span class="hljs-keyword">for</span> (ans&#61;<span class="hljs-number">0</span>;!IDAX(<span class="hljs-number">0</span>);ans&#43;&#43;); <span class="hljs-built_in">printf</span>(<span class="hljs-string">&#34;%d\n&#34;</span>,ans); } <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>; } <script></div><div align="center"><script src="https://www.6miu.com/js/artile.js">$