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

题意

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

题解

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

代码

代码语言：javascript复制

#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;
}

dfs return

0 人点赞