题意:
给一个m<=10^15,每次都减最接近当前值的立方数
让你找一个不大于m的最大的数并且这个数是减法次数最多的数
思路:见http://blog.csdn.net/miracle_ma/article/details/52458715
开始想用贪心直接写
后面发现步数是对的,但使原数最大很难处理,因为各个i^3之间i的差不都<=1
于是用DFS处理
以下是大神题解:
考虑第一块取多少,最大的a3≤m
如果取a,还剩m−a3
取a−1的话,那肯定最大的X是a3−1,剩下a3−1−(a−1)3
如果取a−2的话,肯定没有a−1来的优,因为剩下的比取a−1剩下的要少
所以就是取a或者a−1,然后对于每次剩下的都可以这么考虑
如果你问,剩下x的时候,不是应该要取最大的a么
所以我们开头假设的X,不一定是最终的X
最后根据你取的,重新安排开头的X
比如这会剩x,然后取a−1,x当作了a3−1−(a−1)3
那么只要在最开始的时候X取小一点就行了
所以dfs的时候记录个数,还剩多少,∑a3
var f:array[..]of qword;
n,ans1,ans2:qword;
i:longint; function clac(x:qword):qword;
var l,r,mid,last:qword;
begin
l:=; r:=trunc(sqrt(x)); last:=l;
while l<=r do
begin
mid:=(l+r)>>;
if mid*mid<=x div mid then begin last:=mid; l:=mid+; end
else r:=mid-;
end;
exit(last);
end; procedure dfs(s1,k,s2:qword);
var p:qword;
begin
if s1= then
begin
if (k>ans1)or((k=ans1)and(s2>ans2)) then begin ans1:=k; ans2:=s2; end;
exit;
end;
p:=clac(s1);
dfs(s1-f[p],k+,s2+f[p]);
if p> then dfs(f[p]--f[p-],k+,s2+f[p-]);
end; begin
// assign(input,'1.in'); reset(input);
//assign(output,'1.out'); rewrite(output);
readln(n);
for i:= to do begin f[i]:=i; f[i]:=f[i]*f[i]*f[i]; end;
ans1:=; ans2:=;
dfs(n,,);
writeln(ans1,' ',ans2);
//close(input);
//close(output);
end.