/*
完全背包的变形
背包容量是a，每选一个数字以后背包容量减少a-i*i*i
一共可能的数字有1到i*i*i<=a个
*/
#include<bits/stdc++.h>
using namespace std;
int a,f[1000005];
int main()
{
	cin>>a;
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i*i*i<=a;i++)
	{
		for(int j=0;j<=a;j++)
		{
			if(j-i*i*i>=0) f[j]=min(f[j],f[j-i*i*i]+1);
		}
	}
	cout<<f[a];
	return 0;
}

前言：作者本来想用$dfs$，结果发现数据范围竟然是$1 \le a \le 10^6$，所以我就想换成更快速的算法（其实就是不会优化，因为我的$dfs$可是指数级的，具体时间复杂度我就不细说了，免得浪费时间

好，进入正题，我选择的更快速的算法便是：动态规划

刚开始一看，这东西，怎么这么像完全背包？我再一看，不是完全背包，但是是一个变种，既然确定了是动态规划，那就得推动态转移方程了

首先，先仔细观察，我们设选的数字是$i$，但是，如果$i$大于了$n$的立方根，那就直接退出即可，为什么呢，建议您自行百度

接着，我们设背包体积为$j$ ~ $n$，为什么是$j$ ~ $n$，神犇@不是是$0$ ~ $n$吗？因为我直接把$j$赋值为$i^3$，这样，背包总体积-物品所需空间就会永远$\ge 0$了，也省去了条件判断，接着动态转移方程不就出来了吗？根据子问题推出整体最优解即可，最后动态转移方程为：

$$dp_j = min(dp_j, dp[j - i^3] + 1);$$

这个动态转移方程中的+1是因为这是一个数的立方，并且这个数已经放进了背包，那背包内总物品数量就要加1，最后，$dp_n$就是最后的答案了

整体时间复杂度是小于$O(\sqrt{n}n)$，具体是多少我实在不知道是哪个符号，所以大家见谅

$AC~Code$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int n, dp[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; pow(i, 3) <= n; i++)
        for (int j = pow(i, 3); j <= n; j++)
            dp[j] = min(dp[j], dp[j - i * i * i] + 1);
    cout << dp[n] << endl;
    return 0;
}

严禁抄题解，发现后取消成绩

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。