Codeforces 679B Bear and Tower of Cubes

链接

传送门

题意

给出递推式\(f(x)=f(x-a^3)+1\)(其中\(a\)为满足\(a^3 \leq x\)的最大整数),给出一个\(m(1 \leq m \leq {10}^{15})\),求最大的\(f(x)\)和当\(f(x)\)最大时最大的\(x\)

思路

设所求\(f(x)\)\(F(m)\),对于当前的\(m\),设\(a\)为满足\(a^3 \leq m\)的最大整数,考虑两种转移:

  • 转移至减去\(a^3\)\(F(m)=F(m-a^3)+1\)
  • 转移至减去\({(a-1)}^3\)\(F(m)=F(a^3-1-{(a-1)}^3)+1\)

对于如上两种转移,可以递归求解。如果要转移至减去\({(a-2)}^3\),则变为\(F(m)=F({(a-1)}^3-1-{(a-2)}^3)+1\),由于\(F(m)\)单调不减,且\({(a-1)}^3-1-{(a-2)}^3 < a^3-1-{(a-1)}^3\),所以不考虑此转移。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100010;
LL a[maxn];
LL ansNum, ansX;

void solve(LL m, LL num, LL X) {
if (m == 0) {
if (num > ansNum || (num == ansNum && X > ansX)) {
ansNum = num;
ansX = X;
}
return;
}
LL x = 1;
while (a[x + 1] <= m) {
++x;
}
solve(m - a[x], num + 1, X + a[x]);
if (x > 0) {
solve(a[x] - 1 - a[x - 1], num + 1, X + a[x - 1]);
}
}

int main() {
for (int i = 1; i < maxn; ++i) {
a[i] = LL(i) * i * i;
}
LL m;
scanf("%I64d", &m);
solve(m, 0, 0);
printf("%I64d %I64d\n", ansNum, ansX);
return 0;
}