【题解】UVa 1374【Power Calculus】

分析

上A*,用$d$表示当前深度,$maxd$表示深度上限,则如果当前序列最大的数乘上$2^{maxd-d}$之后仍小于$n$,则剪枝,为了更快接近目标,不应该任选两个数,应该先选较大的数,并且先试加法再试减法。这样做可以在最后一次迭代中快速找到解,从而终止搜索过程。

代码

#include<cstdio>
#include<algorithm>
using std::max;
const int MAXN = 1000 + 6;
int n,A[MAXN];

bool dfs(int d,int maxd){
    if(A[d] == n) return true;
    if(d == maxd) return false;
    int maxv = A[0];
    for(int i = 1;i <= d;i++) maxv = max(maxv,A[i]);
    if((maxv << (maxd - d)) < n) return false;

    for(int i = d;i >= 0;i--){
        A[d + 1] = A[d] + A[i];
        if(dfs(d + 1,maxd)) return true;
        A[d + 1] = A[d] - A[i];
        if(dfs(d + 1,maxd)) return true;
    }
    return false;
}

int solve(int m){
    if(m == 1) return 0;
    A[0] = 1;
    for(int maxd = 1;maxd < 13;maxd++) if(dfs(0,maxd)) return maxd;
    return 13;
}

int main(){
    while(scanf("%d",&n) == 1 && n) printf("%d\n",solve(n));

    return 0;
}