网站开发网站维护这行业怎么样,衡水哪里做网站,美食网站建设项目分析报告,西安免费公司网站设计OD统一考试 题解#xff1a; Java / Python / C 题目描述
一根X米长的树木#xff0c;伐木工切割成不同长度的木材后进行交易#xff0c;交易价格为每根木头长度的乘积。规定切割后的每根木头长度都为正整数,也可以不切割#xff0c;直接拿整根树木进行交易。请问伐木工如… OD统一考试 题解 Java / Python / C 题目描述
一根X米长的树木伐木工切割成不同长度的木材后进行交易交易价格为每根木头长度的乘积。规定切割后的每根木头长度都为正整数,也可以不切割直接拿整根树木进行交易。请问伐木工如何尽量少的切割才能使收益最大化?
输入描述
木材的长度(X50)
输出描述
输出最优收益时的各个树木长度以空格分割按升序排列
示例1
输入
10输出
3 3 4说明
1.一根2米长的树木伐木工不切割为2*1收益最大为2
2.一根4米长的树木伐木工不需要切割为2*2省去切割成本直接整根树木交易为4*1收益最大为4
3.一根5米长的树木伐木工切割为2*3收益最大为 6
4.一根10米长的树木伐木工可以切割为方式: 343也可以切割为方式二:322,3但方式二代木工多切割了一次增加切割成本却卖了一样的价格因此并不是最优收益。题解 动态规划类型的问题。 通过动态规划的方法: 1、定义一个状态数组 dp其中 dp[x] 表示长度为 x 的树木的最大化收益。 2、定义一个数组 d 其中 d[x] 用于记录长度为 x 的树木达到最大收益时最后一节的长度(收益相同取切割次数最少的)。 3、定义 times 其中 times[x] 数组表示长度为x的树木最小需要切割的次数。 动态规划的状态转移方程为dp[x]max(dp[x],dp[j]×(x−j)), for j∈[1,x−1] 这表示尝试对长度为 x 的树木进行切割寻找使收益最大的切割方式。 最后我们通过回溯 d 数组获取切割的具体方式并按升序排列输出。 代码中使用了两个数组 dp 和 d 分别表示最大收益和最后一节的长度遍历计算得到最优解。时间复杂度为 O(X^2)其中 X 为树木的长度。空间复杂度为 O(X)。 Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/*** author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int x scanner.nextInt();// dp[x] 表示长度为 x 的树木最大化的收益int[] dp new int[x 1];// times[x]使长度为 x 的树木最大化的收益最小需要切割的次数int[] times new int[x 1];// d[x] 表示长度为 x 的树木要达到最大收益最后一节的长度int[] d new int[x 1];for (int i 1; i x; i) {// 不切割时的收益dp[i] d[i] i;// 尝试对长度为 i 的树木进行切割以获取最大收益for (int j 1; j i; j) {if (dp[i - j] * j dp[i]) { // 切割出长度 j 的一段判断是否能收益变大d[i] j;dp[i] dp[i - j] * j;times[i] times[i - j] 1;} else if (dp[i - j] * j dp[i] times[i] times[i - j] 1) { // 收益相同但切割次数少d[i] j;times[i] times[i - j] 1;}}}int idx x;ArrayListInteger rs new ArrayList();while (idx 0) {rs.add(d[idx]);idx - d[idx];}Collections.sort(rs);for (int i : rs) {System.out.print(i );}}
}
Python
x int(input())# dp[x] 表示长度为 x 的树木最大化的收益
dp [i for i in range(x 1)]
# 使长度为 x 的树木最大化的收益最小需要切割的次数
times [0] * (x 1)
# d[x] 表示长度为 x 的树木要达到最大收益最后一节的长度
d [i for i in range(x 1)]for i in range(1, x 1):for j in range(1, i): # 尝试对长度为 i 的树木进行切割以获取最大收益if dp[i - j] * j dp[i]: # 切割出长度 j 的一段判断是否能收益变大d[i] jdp[i] dp[i-j] * jtimes[i] times[i-j] 1elif dp[i-j] * j dp[i] and times[i] times[i-j] 1: # 收益相同但切割次数少d[i] jdp[i] dp[i-j] * jtimes[i] times[i - j] 1idx, rs x, []
while idx 0:rs.append(d[idx])idx - d[idx]rs.sort()
print(*rs)
C
#include iostream
#include vector
#include algorithmusing namespace std;int main() {int x;cin x;// dp[x] 表示长度为 x 的树木最大化的收益vectorint dp(x 1);// times[x] 使长度为 x 的树木最大化的收益最小需要切割的次数vectorint times(x 1);// d[x] 表示长度为 x 的树木要达到最大收益最后一节的长度vectorint d(x 1);for (int i 1; i x; i) {// 不切割时的收益dp[i] d[i] i;// 尝试对长度为 i 的树木进行切割以获取最大收益for (int j 1; j i; j) {if (dp[i - j] * j dp[i]) { // 切割出长度 j 的一段判断是否能收益变大d[i] j;dp[i] dp[i - j] * j;times[i] times[i - j] 1;} else if (dp[i - j] * j dp[i] times[i] times[i - j] 1) { // 收益相同但切割次数少d[i] j;times[i] times[i - j] 1;}}}int idx x;vectorint rs;while (idx 0) {rs.push_back(d[idx]);idx - d[idx];}sort(rs.begin(), rs.end());for (int i : rs) {cout i ;}return 0;
}
整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
