题目链接:点击打开链接
简单的搜索技巧与剪枝,不多说了心累,保存路径。。。
//164K 0MS //C++ 1331B #include <cstring> #include <cstdio> int p[6]={100000,10000,1000,100,10,1}; //类似于迷宫方向数组的感觉 int n,sum,dis[6],z; //z为递归的编号,防止重复路径覆盖,每一次递归编号都是不同的 int mx,f,x; struct node { int pi; //前一次递归的编号 int num; //当前的剪出的数字 }q[33]; void dfs(int k,int m,int l,int w) { int i; for(i=l;i<5;i++) //由当前位数开始查找到最后,因为有前导零的情况,所以要记录位数 { int h=m; //当前要剪切的数字 if(k-h/p[i]>=0) { q[++z].pi=w; //记录当前递归的编号 q[z].num=h/p[i]; //记录剪下来的数字 dfs(k-h/p[i],h%p[i],i+1,z); //递归下一次的目标数,剩余数 } } if(m<=k) //若当前数已经不大于当前目标数 { if(mx<n-k+m) //更新mx { q[++z].pi=w; //记录路径 q[z].num=m; x=z;f=0; //返回路径起点编号 mx=n-k+m; } else if(mx==n-k+m) { f=1; //若最大值重复则标记,出现新的最大值时删除标记 } } } int main() { int m,i,j; while(~scanf("%d%d",&n,&m)&&(n||m)) { memset(dis,0,sizeof(dis)); f=0; //重复标记 x=-1; //路径终点编号 z=0; //递归编号 mx=-1; //最接近切割数 for(i=0;i<6;i++) //找出这个数的位数; if(m/p[i]>0) break; dfs(n,m,i,z); //当前目标数,当前数,当前数的位数对应的p数组下标,当前的递归次数 if(mx==-1) printf("error\n"); else if(f) printf("rejected\n"); else { printf("%d ",mx); for(i=x,j=0;i!=0;i=q[i].pi) //顺着前一个的下标从后往前找路径出来 { dis[j++]=q[i].num; } for(i=j-1;i>=0;i--) { printf("%d",dis[i]); if(i) printf(" "); } printf("\n"); } } return 0; } 经历过网络赛心更累了,补了一下注释。