LA 3621 Power Calculus .

题目地址：http://vjudge.net/problem/UVALive-3621

决策就是，之前算过的都能用在这一步的计算，所以把之前的数字全加一遍或者减一遍就好了

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b)  for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
int a[1000+5],n;
bool vis[10000+5];
bool DFS(int cur,int dep){if(cur>dep) return false;else if(a[cur]==n) return true;if(a[cur]<<(dep-cur)<n) return false;REP(i,0,cur) {a[cur+1]=a[cur]+a[i];if(a[cur+1]<=10000&&!vis[a[cur+1]]&&DFS(cur+1,dep)) return true;a[cur+1]=a[cur]-a[i];if(a[cur+1]>0&&!vis[a[cur+1]]&&DFS(cur+1,dep)) return true;}
return false;
}
int main(int argc, char const *argv[])
{while(scanf("%d",&n)==1&&n){REP(maxd,0,(1<<30)){a[0]=1; memset(vis,false,sizeof(vis)); vis[1]=true;if(DFS(0,maxd)) {printf("%d\n", maxd);break;}}}return 0;
}