[置顶] poj1416数字切割解题报告

题意:有一段纸片,就是一个不超过7位数的整数,现在给定你一个目标值 aim ,让你去选择把纸片切成几段,然后这个几段的和值 最接近 aim 且不超过 aim,

分析:

对于这个纸段,比如一个 四位数的 1234,那么第一你就有以下几种切法:  (1、234)  (1、2、34)  (1、2、3、4) (12、34) ().........那么 对于这么多个情况,我们就想一个不重复 的 有顺序的切割方式.....

比如我按照切的次数,第一次....我可以把第一个数字切下来,,,,也可以把第一和第二个数字切下来,那么就如下图有:

[置顶] poj1416数字切割解题报告

那么图中就画出的几个 组合...(1、2、3、4)(1、2、34)(1、23、4)那么可以用一个for循环来处理这个切的过程....然后就按照这个dfs,下面给出代码....

// 164K 0MS
#include<stdio.h>
#include<string.h> int aim;
char shred[7];//要切割的数字,做字符串处理 int max_sum;//最大值次数
int flag_max;//最大值
int shred_sum;//切割次数
int ans[7];//最终结果
int ans_flag[7];//临时结果保存 void dfs(int x,int num,int y)//这里表示我们从第x 位开始切,当前切得值为num,切的次数为 y
{
if(num > aim) return;//寻找不超过目标的最大...那么超过就直接返回
if(x >= strlen(shred))//因为我们从1 开始dfs,那么这里 到刚好 > 的时候就是切出一个答案的时候
{
if(num > flag_max)//比我们标记的最大值还大就更新
{
max_sum = 1;
flag_max = num;
for(int q = 0 ; q < y ; q ++)//这里把ans最终结果先更新
ans[q] = ans_flag[q];
shred_sum = y;
}
else if(num == flag_max)
max_sum = 2;
}
int sum = 0;
for(int i = x ; i < strlen(shred); i ++) //我们从当前的x 位置 一个一个尝试
{
sum *= 10;
sum += shred[i]-'0'; //那么这里就是对于每一次切得到这个值
ans_flag[y] = sum;// 具体的过程,前面有说到的图形解释,后面结合图形有详细说明
dfs(i+1,sum+num,y+1);
}
} int main()
{
int i;
int sum1,sum2;
while(scanf("%d%s",&aim,shred))
{
sum1 = sum2 = 0;
if(aim+(shred[0]-'0') == 0)
break; max_sum = shred_sum = 0;
flag_max = 0;
dfs(0,0,0); if(max_sum == 0)
printf("error\n");
else if(max_sum > 1)
printf("rejected\n");
else
{
printf("%d",flag_max);
for(i = 0 ;i < shred_sum ; i ++)
printf(" %d",ans[i]);
printf("\n");
}
}
return 0;
}

[置顶] poj1416数字切割解题报告
个人愚昧观点...欢迎指正和讨论;;;
[置顶] poj1416数字切割解题报告

上一篇:neutron中创建子网时禁用dhcp服务的问题


下一篇:浏览器 Proxy SwitchyOmega 插件设置代理访问内网服务器