题意:
给你两个数n,m;n表示最大数,m则是需要切割的数。
切割m,使得切割之后的数的和小于等于n。
求出最大的切割方法;
例: 50 12346
12346可以切割为 1 2 34 6和为43,这个数小于n。
12346也可以切割为1 2 3 4 6和为16,这个数也小于n;
但是43大于16,所以去43而不取16;
做法:
dfs(int x,int num,int y)
x代表从第几位开始切割,num代表第x位之前的切割结果,y代表x位之前共切割出来多少个数,是为了储存切割顺序用的。
这样从头到尾进行dfs切割就好啦。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int n,m;
int mlen;
int leap;
int num_max;
int lu[100];
int lu_len;
int lus[100];
int f[8]={0,1,10,100,1000,10000,100000,1000000};
void dfs(int x,int num,int y)
{int sum=0,i;if(num>n)return;if(x>mlen){if(num_max<num){num_max=num;leap=1;for(i=0;i<y;i++){lu[i]=lus[i];lu_len=y;}}else if(num_max==num){leap=2;}return;}for(i=x;i<=mlen;i++){sum=sum*10;sum+=(m/f[mlen-i+1])%10;// printf("sum=%d\n",sum);// if(i!=mlen&&(m/f[mlen-i+1-1])%10==0)// continue;lus[y]=sum;dfs(i+1,num+sum,y+1);}
}
int main()
{int i;while(scanf("%d%d",&n,&m)&&(n||m)){int z;mlen=0;leap=0;num_max=0;z=m;while(z){z=z/10;mlen++;}memset(lu,0,sizeof(lu));memset(lus,0,sizeof(lus));lu_len=0;dfs(1,0,0);if(leap==2)printf("rejected\n");else if(leap==0)printf("error\n");else{printf("%d",num_max);for(i=0;i<lu_len;i++){printf(" %d",lu[i]);}printf("\n");}}return 0;
}