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;
}

支付宝扫码领红包