当前位置: 代码迷 >> 综合 >> poj-1416-Shredding Company-dfs
  详细解决方案

poj-1416-Shredding Company-dfs

热度:98   发布时间:2023-12-19 11:28:18.0

题意:

给你两个数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;
}