【Gym - 101164I】Cubes（dfs，剪枝）---饶文津

题意

将n拆成最少个立方数相加的形式。

题解

根据n的范围，立方数最大不超过400的立方，并且个数也不会很多。 dfs，设置一个深度的上限up。从大到小枚举立方数，剪枝条件：当前层数加上至少还需要的层数>=up就return。

代码#include <cstdio> #include <cstring> using namespace std; int n,c[500],a[101],ans[1001],up=50; void dfs(int d,int x,int k){ if(x==0){ up=d; for(int i=1;i<=d;i++)ans[i]=a[i]; } if(d+1>=up||d+x/c[k]>=up)return; for(int i=k;i;i--)if(c[i]<=x){ a[d+1]=i; dfs(d+1,x-c[i],i); } } int main() { for(int i=1;i<=400;i++)c[i]=i*i*i; scanf("%d",&n); dfs(0,n,400); printf("%dn",up); for(int i=1;i<=up;i++)printf("%d ",ans[i]); return 0; } ---来自腾讯云社区的---饶文津