最新华为OD机试真题-伐木工(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 伐木工(200分) <=

🌍 评测功能需要订阅专栏后私信联系清隆解锁～

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

伐木工

题目描述

K小姐是一位伐木工人，她有一根长度为 米的原木。为了获得最大的收益，她需要将原木切割成若干段，每一段的长度都必须是正整数。

木材交易的规则是，每一段木材的价值等于其长度的平方，而整根原木的价值等于其长度。K小姐最终的收益即为每一段木材价值之和。

现在，请你帮助K小姐计算，要想获得最大收益，她应该如何切割这根原木？

输入格式

输入仅一行，包含一个正整数 ，表示原木的长度。

输出格式

输出若干个正整数，表示切割后每一段木材的长度。你需要按照长度从小到大的顺序输出，相邻两个数之间用一个空格隔开。

如果有多种切割方案都能获得最大收益，你可以输出任意一种。

样例输入

10

样例输出

3 3 4

数据范围

题解

我们可以使用动态规划来解决这个问题。设 表示将长度为 的原木切割后能获得的最大收益。

对于一根长度为 的原木，我们可以选择不切割，此时收益为 ；也可以选择将其切割成两段，长度分别为 和 ，此时收益为 。我们需要枚举所有可能的切割方案，取其中的最大值作为 的值。

最终的答案即为 。在计算出 数组后，我们可以通过倒推的方式找到一种最优的切割方案。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

n = int(input())
f = [0] * (n+1)
for i in range(1, n+1):
    f[i] = i
    for j in range(1, i):
        f[i] = max(f[i], max(j*f[i-j], j*(i-j)))

res = []
m = n
while m >= 1:
    if f[m] == m:
        res.append(m)
        break
    for k in range(m-1, 0, -1):
        if k*(m-k) == f[m]:
            res.append(k)
            res.append(m-k)
            m = 0
            break
        elif k*f[m-k] == f[m]:
            res.append(k)
            m -= k
            break

res.sort()
print(*res)

• Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            f[i] = i;
            for (int j = 1; j < i; j++) {
                f[i] = Math.max(f[i], Math.max(j * f[i - j], j * (i - j)));
            }
        }

        ArrayList<Integer> res = new ArrayList<>();
        int m = n;
        while (m >= 1) {
            if (f[m] == m) {
                res.add(m);
                break;
            }
            for (int k = m - 1; k > 0; k--) {
                if (k * (m - k) == f[m]) {
                    res.add(k);
                    res.add(m - k);
                    m = 0;
                    break;
                } else if (k * f[m - k] == f[m]) {
                    res.add(k);
                    m -= k;
                    break;
                }
            }
        }

        Collections.sort(res);
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i) + " ");
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        for (int j = 1; j < i; j++) {
            f[i] = max(f[i], max(j * f[i - j], j * (i - j)));
        }
    }

    vector<int> res;
    int m = n;
    while (m >= 1) {
        if (f[m] == m) {
            res.push_back(m);
            break;
        }
        for (int k = m - 1; k > 0; k--) {
            if (k * (m - k) == f[m]) {
                res.push_back(k);
                res.push_back(m - k);
                m = 0;
                break;
            } else if (k * f[m - k] == f[m]) {
                res.push_back(k);
                m -= k;
                break;
            }
        }
    }

    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}