最新华为OD机试真题-伐木工(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要订阅专栏后私信联系清隆解锁~
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓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;
}
#华为##华为OD##笔试##春招##秋招#最新华为OD机试-D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测