小米 OJ 《需要多少个立方数?》题解

由 三硝基豆腐 发布

很简单一道 DP 题,很久没写 C++ 了,又有人在群里说这题数据有误,就自己写了下玩玩。

题目链接:https://code.mi.com/problem/list/view?id=44

假设已知$1$到$n$的答案,求$n + 1$的答案是很简单的,枚举立方数,设立方数为$x$,那么$n + 1$的答案就是$n + 1 - x$的答案中最小的那个再加上$1$

复杂度就是$O(n ^ {\frac 4 3})$,$10^6$的数据是没问题的。

(扯了一堆废话,其实就是为了水文章)

对了,事实证明是那人搞错了,而且我敢断定他的程序输入$27$会输出$6$(别问我怎么知道的,我才不会告诉你我一开始也写错了)。

#include <bits/stdc++.h>

#define NS (1000005)
#define TS (105)

using namespace std;

int n, d[NS], t[TS];

int main(int argc, char const* argv[])
{
    for (int i = 1, a; t[i] = INT_MAX, a = i * i * i, a <= 1000000; i += 1)
        t[i] = a;
    scanf("%d", &n);
    if (!n) { puts("1"); return 0; }
    d[1] = 1;
    for (int i = 2; i <= n; i += 1)
    {
        d[i] = INT_MAX;
        for (int j = 1; t[j] <= i; j += 1)
            if (d[i] > d[i - t[j]] + 1)
                d[i] = d[i - t[j]] + 1;
    }
    printf("%d\n", d[n]);
    return 0;
}

仅有一条评论

  1. 呆憨
    呆憨 · 2020-05-19 02:22

    日,我才不会告诉你我连题目都没看懂(皱眉)

发表评论