POJ 1011+HDU1455+NYOJ 293 Sticks
第一眼看到这个题,就想到了深搜,于是兴高采烈的写了起来,超时,后来想了想,优化了一下,剪了一下枝,发现思路有点偏差,后来改改,POJ和HDU过了,NYOJ还超时,Orz,在搜了无数大牛的博客后,终于了解了一种剪枝标记的方法,搜索很简单,就不再解释了,写出来,以后回顾一下,吼吼~~
剪枝方法:(非原创)
越长的木棍对后面木棍的约束力越大,因此要把小木棍排序,按木棍长度从大到小搜索,这样就能在尽可能靠近根的地方剪枝。(剪枝一)
如果当前木棍能恰好填满一根原始木棍,但因剩余的木棍无法组合出合法解而返回,那么让我们考虑接下来的两种策略,一是用更长的木棍来代替当前木棍,显然这样总长度会超过原始木棍的长度,违法。二是用更短的木棍组合来代替这根木棍,他们的总长恰好是当前木棍的长度,但是由于这些替代木棍在后面的搜索中无法得到合法解,当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以,当出现加上某根木棍恰好能填满一根原始木棍,但由在后面的搜索中失败了,就不必考虑其他木棍了,直接退出当前的枚举。(剪枝二)
显然最后一根木棍是不必搜索的,因为原始木棍长度是总木棍长度的约数。(算不上剪枝)
考虑每根原始木棍的第一根木棍,如果当前枚举的木棍长度无法得出合法解,就不必考虑下一根木棍了,当前木棍一定是作为某根原始木棍的第一根木棍的,现在不行,以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功,否则就返回。(剪枝四)
剩下一个通用的剪枝就是跳过重复长度的木棍,当前木棍跟它后面木棍的无法得出合法解,后面跟它一样长度的木棍也不可能得到合法解,因为后面相同长度木棍能做到的,前面这根木棍也能做到。(剪枝五)
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define N 65
using namespace std;
int Stick[N] , Max , sum , n , CC ;
bool flag[N] ;
bool cmp(int a ,int b){
return a > b ;
}
bool DFS( int x , int count , int y ,int l ){
bool sign = ( x == 0 ? true : false ) ;
if( count == CC )
return 1 ;
for( int i = l+1 ; i < n ; i++ ) {
if( !flag[i] ) {
if( Stick[i]+x == y ) {
flag[i] = 1 ;
if( DFS( 0 , count +1 , y , -1) )
return 1 ;
flag[i] = 0 ;
return 0 ;
}
if( Stick[i]+x < y) {
flag[i] = 1 ;
if (DFS( Stick[i]+x , count , y , i ) )
return 1 ;
flag[i] = 0 ;
if(sign)
return 0 ;
while(Stick[i] == Stick[i+1] )
i++ ;
}
}
}
return 0 ;
}
int main(){
while( scanf( "%d" , &n ) , n ){
memset( Stick , 0 , sizeof(Stick) ) ;
sum = 0 ;
for( int i = 0 ; i < n ; i ++ ){
scanf( "%d" , &Stick[i] ) ;
sum += Stick[i] ;
}
sort( Stick , Stick+n , cmp ) ;
for( int i = Stick[0] ; i <= sum ; i++ ) {
if( sum%i == 0 ) {
memset( flag , 0 , sizeof(flag) ) ;
CC = sum/i ;
if( DFS( 0 , 0 , i , -1) ) {
printf( "%d\n" , i ) ;
break ;
}
}
}
}
return 0 ;
}
分享到:
相关推荐
北大POJ1011-Sticks 解题报告+AC代码
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
详细解释 ,既有源代码又有书面文字解释,ppt,在VC6上完成
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
很详尽的讲述了简单的深搜,宽搜算法,另外还有剪枝策略,另外附加了poj上的题目举例分析。 (作者:东北师大计算机学院程文华)
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
NULL 博文链接:https://128kj.iteye.com/blog/1750462
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
北大POJ初级-简单搜索 解题报告+AC代码
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
cpp代码-2.24.1 poj 1011