Gym - 101164I————Cubes（上限深搜+剪枝）
原题：
把一个数分解为尽可能少的数的立方和。
因为是立方和，所以如果深搜的话深度不会很大。所以可以设置一个上限进行爆搜，并且加入剪枝操作。
不过这个深度得好好考虑，剪枝也会卡比较小的地方。
实践证明50层是可以过的。
#include <cstdio>
using namespace std;
const int MAXN=1000;
int res[MAXN];
int cube[MAXN];
int n;
int up=50;
int temp[MAXN];
void dfs(int cur,int r,int MAX){
if(r==0){
if(cur<up){
for(int i=1;i<=cur;i++)
res[i]=temp[i];
up=cur;
}
return;
}
if(cur+1>=up||cur+r/cube[MAX]>=up){
return;
}
for(int i=MAX;i>=1;i--){
if(cube[i]>r)
continue;
temp[cur+1]=i;
dfs(cur+1,r-cube[i],i);
}
return;
}
int main(){
for(int i=1;i<=360;i++){
cube[i]=i*i*i;
}
scanf("%d",&n);
dfs(0,n,360);
printf("%d
",up);
for(int i=1;i<=up;i++)
printf("%d%c",res[i],i==up?
: );
}
下一篇：
二叉树的遍历（递归遍历方法）