POJ 1011

本文主要是介绍POJ 1011，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

利用dfs搜索，自己尝试想了好久没有理解，最后还是按照别人的题解写出来一份，中间有一些必要的剪枝优化

后面使用桶排序的思路，将原有代码大幅优化

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn= (1<<6)+3;
const int maxm= 53;

int n;
int stk[maxm];

int cmp(int lhs, int rhs)
{
	return lhs> rhs;
}
int dfs(const int lth, int c_l, int res, int cnt)
{
	--stk[c_l];
	res-= c_l;
	if (res){
		for (int i= min(res, c_l); i> 0; --i){
			if (stk[i] && dfs(lth, i, res, cnt+1)){
				return 1;
			}
		}
	}
	else{
		if (n== cnt){
			return 1;
		}
		for (int i= 50; i> 0; --i){
			if (stk[i]){
				if (dfs(lth, i, lth, cnt+1)){
					return 1;
				}
				break;
			}
		}
	}
	++stk[c_l];

	return 0;
}
int Search(const int sum, const int mx)
{
	const int h_sum= sum>>1;
	for (int i= mx; i<= h_sum; ++i){
		if (sum%i){
			continue;
		}
		if (dfs(i, mx, i, 1)){
			return i;
		}
	}

	return sum;
}

int main(int argc, char const *argv[])
{
	int sum;
	int x, mx;
	while (~scanf("%d", &n) && n){
		sum= mx= 0;
		memset(stk, 0, sizeof(stk));
		for (int i= 0; i< n; ++i){
			scanf("%d", &x);
			if (x> mx){
				mx= x;
			}
			sum+= x;
			++stk[x];
		}

		printf("%d\n", Search(sum, mx));
	}
	return 0;
}

这篇关于POJ 1011的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！