我们可以这样考虑
X 必定是由若干个立方数拼起来的 因此我们可以逆着求 只需关心每次取哪个立方数即可
设a是最大的 a 使得 a^3 不超过 m
分析样例 我们发现在第一次的时候 就可以取a或者a-1
那第一次取a-2 a-3....行不行呢？
1.用 a，剩下m-a^3 2.用 a-1, X 最大为 a^3-1, m2 = a^3-1-(a-1)^3=a^2-a 3.用 a-2, X 最大为(a-1)^3-1,m2=(a-1)^3-1-(a-2)^3=a^2-3a+6 ...... 显然 2 一定比 3 优
因此第一次只能取a或者a-1，那后来怎么办呢？
其实后面的每一次都是从a，a-1里选，因为让每一步抉择都最优（X最大），类似于dp思想，总的才会最优
代码不保证正确性，经供参考
#include<bits/stdc++.h> #define ll long long using namespace std; ll m; pair<ll,ll> ans; ll pow3(ll x) { return x*x*x; } void search(ll m,ll step,ll spend) { if(m==0) { ans=max(ans,make_pair(step,spend)); return; } ll x=1; while(pow3(x+1)<=m) x++; search(m-pow3(x),step+1,spend+pow3(x)); search(pow3(x)-1-pow3(x-1),step+1,spend+pow3(x-1)); } int main() { cin>>m; search(m,0,0); cout<<ans.first<<'\n'<<ans.second; return 0; }