Sample test(s)
input
9
output
91 1 1 1 1 1 1 1 1
input
32
output
310 11 11 题意：给出一个数n，，输出m个数相加等于n，并且使得m最小，而且所有的数只能由0,1组成思路，由只有0,1两个数字可以联想到二进制，0->0, 01->1, 10->2, 11->3……，所以把十进制转换成二进制进行搜索即可。#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>using namespace std;int minn;int n;int p[100100],b[100010];int v[1000100];void DFS(int pn,int cnt){//printf("pn = %d minn = %d cnt = %d\n",pn,minn,cnt);if(cnt>=minn){return ;}if(pn == 0){if(minn>cnt){minn = cnt;for(int i=0;i<cnt;i++){b[i] = p[i];}}return ;}for(int i=65; i>=1; i–){int pi = i;int r = 1;int sum = 0;while(pi){sum += (pi%2)*r;r = r*10;pi = pi/2;}if(sum<=pn){p[cnt] = sum;if(cnt+1<v[pn-sum]){DFS(pn-sum,cnt+1);v[pn-sum] = cnt + 1;}}}}int main(){while(scanf("%d",&n)!=EOF){for(int i=0;i<=1000001;i++){v[i] = 9999999;}minn = 999999;DFS(n,0);printf("%d\n",minn);for(int i=minn-1;i>=0;i–){if(i == 0){printf("%d\n",b[i]);break;}printf("%d ",b[i]);}}return 0;}
最好的节约是珍惜时间，最大的浪费是虚度年华。
