Description
Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.
Input
The first line of the input contains integer n (1?≤?n?<?1015).
Output
Print expected minimal number of digits 1.
Sample Input
121
6
题意：给出一个数n，要求用1组成的数来得到n，问最少要使用多少个1
一开始想的很简单，只要每对于每位数都用1消去，后来想到要达到某一个数字，有两种方法：
1：有与它同位的1...1组成； 2 由比它大一位的1...1减去和它同位的1....1组成。
只能使用dfs遍历所有情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL __int64
LL a[17] ;
LL f(LL n,LL i)
{
LL num = n / a[i] ;
n %= a[i] ;
if(n == 0)
return num*i ;
else
return num*i + min( i+f(a[i]-n,i-1),f(n,i-1) );
}
int main()
{
LL n , i ;
a[0] = 0 ;
for(i = 1 ; i <= 16 ; i++)
a[i] = a[i-1]*10 + 1 ;
scanf("%I64d", &n);
printf("%I64d\n", f(n,16));
}
CodeForces 440C One-Based Arithmetic(递归，dfs),布布扣,bubuko.com
CodeForces 440C One-Based Arithmetic(递归，dfs)
原文：http://blog.csdn.net/winddreams/article/details/38735787