poj 1416 (hdu 1539）Shredding Company：剪枝搜索

点击打开链接

题目大意是有一个分割机，可以把一串数字分割成若干个数字之后求和，题目输入一个数字上界和待分割的数字，让我们求出分割后数字之和在不超过给定max的情况下的最大值，并且给出分割方案，如果没有分割方案，则输出error，如果有多种方案则输出rejected。

这是个搜索题，深搜就可以求解，但是有一些剪枝的方案，题目讨论区说貌似不剪枝也能过，没试过，我一开始就写了有剪枝的，下面说一下一些剪枝方案：

假设题目输入格式为max number

1，如果number各个位相加以后仍然大于max，则error，这是在搜索之前判断的

2，如果number <= max 那么number就是切割方案，因为number能切出来的最大数是它本身，最小数就是各位之和了

3.，搜索过程中动态改变下界，如果我们之前搜索过的结果中有一个结果ans出现了，那么当我们搜索时，我们首先判断前面所有裁剪的总和sum和剩下的那一段x的和，如果小于之前求出的ans，那么后面将不再拆分 x 因为再怎么拆分也不会得到更接近max的ans了，相反，如果sum + x大于ans并且小于max，那么直接把ans更新为sum + x，也不用继续裁剪x了，因为x裁剪出来的也必定小于x，所以这个剪枝个人感觉还是比较强力的，只有sum + x > max的时候才能往下搜索，需要注意的是104会分成1
0 4和1 04，同样也会有140分解成1 4 0的问题，所以我用了两个标记来区分这两种情况，所以写的比较绕

0MS代码：

#include<stdio.h>

int stack[20];

int max;

int top;

int len;

bool f;

int ans[20];

void dfs(int it, char * num, int sum, int n)

{

	if(!num[it])

		return ;

	int i;

	int numb = 0;

	for(i = it; num[i]; i++)

	{

		int j;

		bool mark = false;

		numb = 0;

		int number;

		for(j = it; j <= i; j++)

		{

			numb *= 10;

			numb += num[j] - '0';

		}

		if(num[i + 1] == '0' && num[i + 2] != 0)

			mark = true;

		if(num[i + 1] != 0)

			sscanf(num + i + 1, "%d", &number);

		else

			number = 0;

		if(number + numb + sum < max)

			continue;

		else if(number + numb + sum == max)

			f = true;

		else if(number + numb + sum > max && number + numb + sum <= n)

		{

			max = number + numb + sum;

			if(mark == true)

				f = true;

			else

				f = false;

			stack[top ++] = numb;

			stack[top ++] = number;

			for(j = 0; j < top; j++)

				ans[j] = stack[j];

			len = top;

			top -= 2;

			continue;

		}

		stack[top++] = numb;

		dfs(i + 1, num, sum + numb, n);

		top --;

	}

}

int main()

{

	int n, m;

	char num[20];

	while(scanf("%d %d", &n, &m), n + m != 0)

	{

		if(m <= n)

		{

			printf("%d %d\n", m, m);

			continue;

		}

		sprintf(num, "%d", m);

		int i;

		int sum = 0;

		for(i = 0; num[i]; i++)

		{

			sum += num[i] - '0';

		}

		if(sum > n)

		{

			printf("error\n");

			continue;

		}

		top = len = 0;

		max = -1;

		f = false;

		dfs(0, num,0, n);

		if(f == false)

		{

			printf("%d", max);

			for(i = 0; i < len; i++)

				printf(" %d", ans[i]);

			printf("\n");

		}

		else

			printf("rejected\n");

	}

	return 0;

}

巴特西

poj 1416 (hdu 1539）Shredding Company：剪枝搜索

最新文章

热门文章