唯一一篇题解在说什么啊，我还是来写一篇正常一点的吧。
注意，翻译的时候少了点什么，原题保证 $n \le 10^5$。
考虑 dp。定义 $dp_i$ 为将 $i$ 表示出来所需最少数字数。初始化为 $+ \infty$。
显然有 $dp_0=0$。
对于 $dp_i$，枚举每一个正整数 $j$ 使得 $j^3 \le i$。则 $dp_i = \min(dp_i,dp_{i-j^3})$。意义为从 $i-j^3$ 的结果再拼一个 $j^3$ 得到 $i$。
时间复杂度是 $O(n \log_3 n)$ 的。
:::info[Code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int main(){
int n;
int id=0;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=100000;i++){
for(int j=1;j*j*j<=i;j++){
dp[i]=min(dp[i],dp[i-j*j*j]+1);
}
}
while(cin>>n){
id++;
printf("Case #%d: %d\n",id,dp[n]);
}
}
|
:::