POJ 1011
这两天没怎么做题,重新研究了一下一道深搜题,那个是当初讲剪枝的时候的例题,也就是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;
}