首页 > 代码库 > CodeForces 440C One-Based Arithmetic(递归，dfs)
CodeForces 440C One-Based Arithmetic(递归，dfs)
A - One-Based Arithmetic
Time Limit:500MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Appoint description:
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
Input
121
Output
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 __int64LL 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));}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。