항 저 우 전기 hdu 1455 sticks 깊이 우선 검색

http://acm.hdu.edu.cn/showproblem.php?pid=1455
전형 적 인 문 제 는 사람의 뇌 를 가장 연습 하 는 것 이 라 고 한다. 이 문 제 는 바로 깊이 우선 산법 의 정 수 를 이해 하고 유연 하 게 활용 해 야 한 다 는 것 이다. 본 문 제 는 바로 나의 지능 을 시험 하 는 문제 이다.결국 다른 사람의 코드 를 시험 하고 나 서 야 자신의 코드 를 썼 다.

//      
#include 

using namespace std;

#include 
#include 
#include 

int sticks[65];
bool used[65], flag;

int n, len, piece;

bool cmp(int a, int b)
{
	return a > b;
}

void dfs(int pos, int cur, int cnt)
{
	if(flag)return ;//          
	if(cur == len){
		cnt ++;
		if(cnt == piece){//     
			flag = true;
		}
		dfs(0,0,cnt);
		return ;
	}
	if(pos == n)return ;//       stick
	int pre = -1;
	for(int i = pos; i < n; i ++){// pos       
		if(!used[i] && sticks[i] != pre && cur + sticks[i] <= len){
			pre = sticks[i];
			used[i] = true;
			dfs(i + 1, sticks[i] + cur, cnt);
			used[i] = false;
			if(flag||pos==0)return;
		}
	}
}

int main()
{
//	freopen("input.txt", "r+", stdin);
	int i;
	int sum, max;
	while(scanf("%d", &n)&&n){
		sum = 0;
		for(i = 0; i < n; i ++){
			scanf("%d", &sticks[i]);
			sum += sticks[i];
		}
		sort(sticks, sticks+n, cmp);//    
		max = sticks[0];
		for(i = max; i <= sum; i ++){//i        sitck   
			if(sum%i==0){
				piece = sum/i;//stick    
				len = i;
				memset(used, false, sizeof(used));
				flag = false;
				dfs(0,0,0);
				if(flag)break;
			}
		}
		printf("%d
", len);
	}
	return 0;
}

테스트 를 통 해 일부 시스템 에 서 는 시간 을 초과 할 수도 있 고 계속 가 지 를 자 르 고 마침내 AC 2000 여 ms 가 되 었 다.

#include 

using namespace std;

#include 
#include 
#include 

int cmp(const void *a, const void *b)
{
	return (*(int *)b)-(*(int *)a);
}

bool used[65];
int sticks[65];
int n, len, piece;

bool dfs(int pos, int cur, int cnt)
{
	bool flag = (cur==0 ? true : false);
	if(cnt == piece){
		return true;
	}
	for(int i = pos; i < n; i ++){
		if(used[i])continue;
		if(cur + sticks[i] == len){
			used[i] = true;
			if(dfs(0,0,cnt+1))return true;
			used[i] = false;
			return false;
		}
		else if(cur + sticks[i] < len){
			used[i] = true;
			if(dfs(i+1, cur+sticks[i], cnt))
				return true;
			used[i] = false;
			if(flag)return false;
			while(sticks[i] == sticks[i+1])i++;
		}
	}
	return false;
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int sum, i;
	while(scanf("%d", &n)&&n){
		sum = 0;
		for(i = 0; i < n; i ++){
			scanf("%d", &sticks[i]);
			sum += sticks[i];
		}
		qsort(sticks, n, sizeof(sticks[0]), cmp);
//		printf("%d
", sticks[n-1]);
		memset(used, false, sizeof(used));
		for(len = sticks[0]; len <= sum; len ++){
			if(sum%len==0){
				piece = sum/len;
				if(dfs(0,0,0)){
					printf("%d
", len);
					break;
				}
			}
		}
	}
	return 0;
}