华为 OD 机试 C++ 题解：木材切割收益最大化

题目描述

一根 X 米长的树木，伐木工需要将其切割成若干段不同长度的木材进行交易。交易规则是每根木头长度的乘积即为总收益。规定切割后的每根木头长度必须为正整数；也可以选择不切割，直接拿整根树木进行交易。

核心目标是：在确保收益最大化的前提下，尽量减少切割次数（即段数最少）。

输入描述

木材的长度（X ≤ 50）

输出描述

输出最优收益时的各个树木长度，以空格分隔，按升序排列。

解题思路

这是一个典型的动态规划问题，类似于经典的'切棒问题'（Rod Cutting Problem），但增加了一个约束条件：在收益相同的情况下，优先选择段数更少的方案。

状态定义

我们定义 dp[i] 为长度为 i 的木材所能获得的最大收益。为了处理'尽量少切割'的要求，我们需要同时记录达到该收益时的最少段数。因此，状态可以设计为一个结构体或 pair，包含 {max_profit, min_segments}。

状态转移

对于长度为 i 的木材，我们可以尝试从 1 到 i-1 的位置进行第一次切割。假设第一段长度为 j，剩余部分长度为 i-j。

此时有两种情况：

1. 不再切割剩余部分：收益为 j * (i - j)，段数为 2。
2. 继续切割剩余部分：收益为 j * dp[i-j].profit，段数为 dp[i-j].segments + 1。

我们需要遍历所有可能的 j，比较哪种方案更优。比较规则如下：

• 优先比较收益大小，收益大者优。
• 若收益相同，则比较段数，段数少者优。

路径回溯

由于题目要求输出具体的切割长度，而不仅仅是最大收益值，我们在 DP 过程中需要记录决策路径。可以使用一个 path[i] 数组，记录当长度为 i 时，第一段切割的长度是多少。计算完 DP 表后，从 X 开始根据 path 数组回溯，即可还原出所有的切割段。

代码实现

下面给出完整的 C++ 实现。注意处理边界情况，比如不切割的情况（即整根出售）。

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

using namespace std;

// 定义状态结构体，存储最大收益和对应的最少段数
struct State {
    long long profit;
     segments;
};

{
     X;
     (!(cin >> X))  ;

    
    ;
    
    ;

    
    dp[] = {, };

     ( i = ; i <= X; ++i) {
        
        dp[i] = {( )i, };
        path[i] = i;

        
         ( j = ; j < i; ++j) {
            
              profitA = ( )j * (i - j);
             segsA = ;

            
              profitB = ( )j * dp[i - j].profit;
             segsB = dp[i - j].segments + ;

            
             (profitA > dp[i].profit || (profitA == dp[i].profit && segsA < dp[i].segments)) {
                dp[i] = {profitA, segsA};
                path[i] = j;
            }

            
             (profitB > dp[i].profit || (profitB == dp[i].profit && segsB < dp[i].segments)) {
                dp[i] = {profitB, segsB};
                path[i] = j;
            }
        }
    }

    
    vector<> result;
     curr = X;
     (curr > ) {
         cut = path[curr];
        result.(cut);
        curr -= cut;
    }

    
    (result.(), result.());
     ( i = ; i < result.(); ++i) {
        cout << result[i] << (i == result.() -  ?  : );
    }
    cout << endl;

     ;
}