【POJ3134】 Power Calculus [迭代加深]

挺水的，像我这种小蒟蒻都能写出来， emmmm主要没想到那个乐观估计剪枝，看了题解才知道迭代加深的乐观估计剪枝

POJ不支持万能头文件 POJ不支持万能头文件 POJ不支持万能头文件！！！

我交了四遍，后面发现不支持万能头文件（脏话）就很气，然后听了csy的复制了一篇题解的前面过了，气气

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1000+10;
 4 int n,m[N],ans;
 5 int rd()
 6 {
 7     int x=0,w=0;char ch=0;
 8     while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
 9     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
10     return w?-x:x;
11 }
12 
13 bool dfs(int x,int cnt)
14 {
15     if(x<<(ans-cnt)<n) return false;//乐观估计剪枝 如果一直按最大的方案还是无法到达n则不成立 
16     if(cnt>ans) return false;//达到最大深度 
17     if(x==n) return true; //找到了
18     m[cnt]=x;
19     for(int i=0;i<=cnt;i++)
20     {
21         if(dfs(x+m[i],cnt+1)) return true;
22         if(dfs((x>m[i])?x-m[i]:m[i]-x,cnt+1)) return true;
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     n=rd();
30     while(n)
31     {
32         memset(m,0,sizeof(m));
33         ans=0;
34         while(!dfs(1,0))
35         {
36             ans++;
37             memset(m,0,sizeof(m));
38         }
39         printf("%d
",ans);
40         n=rd();
41     }
42     return 0; 
43 }