塔
题目描述 小A想搭一个体积不超过m的塔，他有各种大小的立方体积木，比如边长为a（a为整数）的积木，体积为 a3 ，现在小A需要你给一个塔的体积X（X<=m），每次小A会用一个能用的（即：使塔的总体积不超过X的）最大的积木，依次到搭好为止，现在他想最大化积木的个数，同时在积木个数最大的情况下使X最大。
输入描述 一行一个数m
输出描述 一行两个数，最多积木数以及X。
样例输入 48
样例输出 9 42
样例解释 X=23或42时都用了9块积木， 42=33+23+7∗13
数据范围 30%：m<= 105 50%：m<= 1010 100%：m<= 1015 （对题目描述有删改）
拿到题还是先看数据规模。对于30%的数据，我们可以用一个数组保存当体积为X时用的积木数，再计算当体积小于等于X时用的积木数。然而，这道题的最大数据规模决定了这道题不需要任何预处理，因为不可能预处理完。所以我们来考虑一下推导。
我们可以知道，当塔的体积为X时，用的第一块积木只能是边长为 ⌊3X−−√⌋ 的积木。反过来，若用的第一块积木的边长为a，则塔的体积最多为 (a+1)3−1 。我们还能用DP思想得到下面这个结论：当我们要搭一个体积为X的塔时，我们相当于用一块边长为 ⌊3X−−√⌋ 的积木并搭一个体积为 X−⌊3X−−√⌋ 的塔。 我们可以设 f(x)=max{count(1,2,...,x)} （即当m=x时的答案）。由贪心思想可知，x越大，答案不会越小，所以我们可以看看用什么大小的积木最合适。发现， m−a3 和 a3−1−(a−1)3 之间的关系是不确定的，但是 a3−1−(a−1)3 恒大于 (a−1)3−1−(a−2)3 ，所以我们只需要判断 f(m−a3) 和 f(a3−1−(a−1)3) 哪个最优。注意，虽然求f可以直接选择参数大的那个求解，但是题目要求求x，而x哪个大还不能确定，所以必须算到底。
参考代码
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; inline int readIn() { int a; scanf("%d", &a); return a; } typedef unsigned long long ll; ll m; ll turt(ll num) { ll l = 1, r = 1e5+1; while(r - l > 1) { ll mid = l + (r - l) / 2; if(mid * mid * mid < num) { l = mid; } else { r = mid; } } if((l + 1) * (l + 1) * (l + 1) <= num) l++; return l; } int f(ll m, ll& x) { ll a = turt(m); if(a == 1) { x += m; return m; } ll y = 0,z = 0; int ans1 = f(m - a*a*a,y) + 1; int ans2 = f(a*a*a - 1 - (a-1)*(a-1)*(a-1), z) + 1; if(ans1 >= ans2) { x = a*a*a + y; return ans1; } else { x = (a-1) * (a-1) * (a-1) + z; return ans2; } } void run() { cin >> m; ll x = 0; printf("%d ", f(m, x)); cout<<x<<endl; } int main() { run(); return 0; }