- 首页 > it技术 > >
// by BNU_LZM
#include
#include
using namespace std;
const int maxn = 1010;
int ans[maxn], n;
bool dfs(int d, int maxd)
{
if(ans[d] == n) return true;
if(d == maxd) return false;
int m = 0;
for(int i = 0;
i <= d;
i++) m = max(m, ans[i]);
if((m << (maxd-d)) < n) return false;
for(int i = d;
i >= 0;
i--)
{
ans[d+1] = ans[d]+ans[i];
if(dfs(d+1, maxd)) return true;
ans[d+1] = ans[d]-ans[i];
if(dfs(d+1, maxd)) return true;
}
return false;
}int solve()
{
if(n == 1) return 0;
ans[0] = 1;
for(int maxd = 1;
;
maxd++)
{
if(dfs(0, maxd)) return maxd;
}
}int main()
{
scanf("%d", &n);
printf("%d", solve());
return 0;
}
推荐阅读
