CF 679B

• 长智商的题目…
  @ 题意：有无穷多个立方体，立方体的边长都是正整数，给定一个$m(10^{15})$,然后让你选取一个$X<=m$作为你要堆砌的体积的大小,堆砌的时候每次必须选择最大的立方体来填充。问题是让你选定的X所用的立方体最多，满足这个条件下，使得X尽可能的大。

  @ 思路：状态转移方程挺容易想到 : $dp[i] = dp[i - a^3] + 1$,其中$i$是体积，$a$是满足$a^3 <= m$的最大的正整数。 但是 $m$ 大的一比，显然不能直接转移。观察到$m$正好是$100000$的立方，大体可以猜到怎样的一个复杂度。进一步分析，我们所选择的X的取值区间其实是在$[(a-1)^3,m]$这个区间内, 这一点我们可以用反证法证明 : 如果$X$作为答案，比这区间的数要小，那么完全可以再加上$(a-1)^3$这个立方体, 这样就可以比这个答案多一个，与$X$是答案矛盾。那么就可以知道，$X$要么取$[(a-1)^3, a^3]$, 要么取$[a^3, m]$，如果取前者，$m$就变成了$a^3-1$, 否则就是$m-a^3$，然后你可以发现其实最多最多用到边长为$[1,100000]$的立方体每个一次，而且这是个自顶向下的过程，所以用个记忆化搜索搞搞就行了。

#include <map>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
const int maxn = 100007;
long long cub[maxn], count;
std::map<long long, std::pair<int, long long> > dp;
std::pair<int, long long> find(long long x){
    if(x <= 7) return {x, x};
    int x1, x2; long long y1, y2;
    count ++;
    if(dp.find(x) != dp.end()) return dp[x];
    int k = std::upper_bound(cub, cub + 100003, x) - cub - 1;
    std::tie(x1, y1) = find(x - cub[k]);
    std::tie(x2, y2) = find(cub[k] - 1);
    return dp[x] = std::max(std::make_pair(x1 + 1, y1 + cub[k]), std::make_pair(x2, y2));
}
int main()
{
    long long m;
    std::cin >> m;
    for(long long i = 1; i < maxn; i ++){
        cub[i] = i * i * i;
    }
    auto ans = find(m);
    std::cout << ans.first << ' ' << ans.second << '\n';
}