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

饶文津

发布于 2020-06-02 12:10:59

2500

发布于 2020-06-02 12:10:59

文章被收录于专栏：饶文津的专栏饶文津的专栏

题意

将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("%d\n",up);
	for(int i=1;i<=up;i++)printf("%d ",ans[i]);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-02-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs