这两天没怎么做题,重新研究了一下一道深搜题,那个是当初讲剪枝的时候的例题,也就是POJ1011

题目大意:

一组等长的木棒,将它们随机地裁断,使得每一节木棍的长度都不超过50个长度单位。然后又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。求原始木棒的可能最小长度。

#include <stdio.h>
#include <stdlib.h>

	int n,sum,stick[66];
	bool stick_used[66],lsti;

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

bool dfs(	int left,/*所有剩下的长度*/
			int lookingfor,/*当前要找到一小段长度*/
			int perlenth/*每段长度*/){
	printf("%d %d %d n",left,lookingfor,perlenth);getchar();
	if(left==0)return true;
	if(lookingfor==0){
		lsti=0;
		return dfs(left,perlenth,perlenth);
	}
	int i;
	for(i=lsti;i<n;i++){
		if(!stick_used[i]&&stick[i]<=lookingfor){
			stick_used[i]=true;
			lsti=i;
			printf("i=%dn",i);
			if(dfs(left-stick[i],lookingfor-stick[i],perlenth)){
			//	printf("use->%dn",stick[i]);
				return true;
			}
			stick_used[i]=false;
			if(lookingfor==perlenth
			/*如果找的是一根木棒的第一个部分,没找到,就没必要往下找了,
			因为,以后还是会用到这个没找到组合的这个木棒的*/
			||lookingfor==stick[i]
			/*同样的,要找到长度就是这根木棒,发现后面的都配不上了
			,这个长度肯定要有的,所以往下找也没用了*/)return false;
		}
	}
	return false;
}

int main(){
	int i;
	while(scanf("%d",&n),n!=0){
		for(i=sum=0;i<n;i++){
			scanf("%d",&stick[i]);
			sum+=stick[i];
			stick_used[i]=false;
		}
		qsort(stick,n,sizeof(int),cmp);
		for(i=0;i<n;i++)printf("%d ",stick[i]);
		printf("sum:%dn",sum);
		for(i=stick[0];i<=sum;i++){
			if(sum%i==0){
				lsti=0;
//				printf("n%dn",i);
//				getchar();
				if(dfs(sum,i,i)){
					printf("%dn",i);
					break;
				}
			}
		}
	}
	return 0;
}

代码注释,已经说明了具体的思想了,我也不想赘述。

另外,还有一道水题,实在水得没意思那种,POJ3749

#include <stdio.h>

int main(){
	char c,code[]="VWXYZABCDEFGHIJKLMNOPQRSTU";
	while(1){
		if(getchar()=='E')break;
		while((c=getchar())!='n');
		while((c=getchar())!=EOF){
			if(c>='A'&&c<='Z')
				putchar(code[c-'A']);
			else
				putchar(c);
			if(c=='n')break;
		}
		if(c==EOF)break;
		while(getchar()!='n');
	}
	return 0;
}