链接
传送门
题意
给出递推式\(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;
}
|