题目描述：
给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：
- 沿垂直方向按高度 完全 切割木块，或
- 沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。
请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。
注意你可以切割木块任意次。
数据范围：
$1\le m, n \le 200, 1\le prices.len \le 2\times 10^4$
题解：
直接设 $dp[i][j]$ 表示长度为 $i$ ，宽度为 $j$ 的木块卖完之后的最大价值。然后可以枚举切分这块木板，枚举横着切，竖着切。
四层循环。
需要使用 $hash$ 表记录一下目标木板。如果当前的 $i,j$ 是目标木板，直接更新一下价值，然后再枚举切分。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
struct PairHash
{
template <class T, class U>
size_t operator()(const pair<T, U> &p) const
{
return hash<T>()(p.first) ^ hash<U>()(p.second);
}
};
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
long long sellingWood(int m, int n, vector<vector<int>> &prices)
{
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1));
unordered_map<pair<int, int>, int, PairHash> mp;
for (auto &price : prices)
mp[{price[0], price[1]}] = price[2];
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (mp.count({i, j}))
dp[i][j] += mp[{i, j}];
for (int r = 1; r < i; ++r)
dp[i][j] = max(dp[i][j], dp[r][j] + dp[i - r][j]);
for (int c = 1; c < j; ++c)
dp[i][j] = max(dp[i][j], dp[i][c] + dp[i][j - c]);
}
}
return dp[m][n];
}
};
|