phpcms 移动网站模板,哈尔滨企业自助建站系统,诸城网站建设定制,网站开发新闻本文涉及知识点
记忆化搜索
LeetCode2312. 卖木头块
给你两个整数 m 和 n #xff0c;分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices #xff0c;其中 prices[i] [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
每…本文涉及知识点
记忆化搜索
LeetCode2312. 卖木头块
给你两个整数 m 和 n 分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices 其中 prices[i] [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
每一次操作中你必须按下述方式之一执行切割操作以得到两块更小的矩形木块
沿垂直方向按高度 完全 切割木块或 沿水平方向按宽度 完全 切割木块 在将一块木块切成若干小木块后你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块来交换它的高度值和宽度值。
请你返回切割一块大小为 m x n 的木块后能得到的 最多 钱数。
注意你可以切割木块任意次。
示例 1 输入m 3, n 5, prices [[1,4,2],[2,2,7],[2,1,3]] 输出19 解释上图展示了一个可行的方案。包括
2 块 2 x 2 的小木块售出 2 * 7 14 元。1 块 2 x 1 的小木块售出 1 * 3 3 元。1 块 1 x 4 的小木块售出 1 * 2 2 元。 总共售出 14 3 2 19 元。 19 元是最多能得到的钱数。 示例 2
输入m 4, n 6, prices [[3,2,10],[1,4,2],[4,1,3]] 输出32 解释上图展示了一个可行的方案。包括
3 块 3 x 2 的小木块售出 3 * 10 30 元。1 块 1 x 4 的小木块售出 1 * 2 2 元。 总共售出 30 2 32 元。 32 元是最多能得到的钱数。 注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。
提示
1 m, n 200 1 prices.length 2 * 104 prices[i].length 3 1 hi m 1 wi n 1 pricei 106 所有 (hi, wi) 互不相同 。
记忆化搜索
vW1[h][w] 表示高为h宽为w的木块不切割能买的价格。为0表示无法买出。 vW[h][w] 表示最大卖出价格0表示无法卖出-1表示未处理。 状态转移未处理 垂直切 wW[h][w] M a x x : 1 h − 1 ( M S ( x , w ) M S ( h − x , w ) ) \large Max_{x:1}^{h-1}(MS(x,w)MS(h-x,w)) Maxx:1h−1(MS(x,w)MS(h−x,w)) 水平切 wW[h][w] M a x x : 1 w − 1 ( M S ( h , x ) M S ( h , w − x ) ) \large Max_{x:1}^{w-1}(MS(h,x)MS(h,w-x)) Maxx:1w−1(MS(h,x)MS(h,w−x)) 初始状态vW为-1。 返回值MS(h,w)。
代码
核心代码
templateclass ELE, class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft, (ELE)other);
}templateclass ELE
void MaxSelf(ELE* seft, const ELE other)
{*seft max(*seft, other);
}class Solution {
public:long long sellingWood(int m, int n, vectorvectorint prices) {m_vW1.assign(m 1, vectorint(n 1));for (const auto v : prices) {m_vW1[v[0]][v[1]] v[2];}m_vW.assign(m 1, vectorlong long(n 1,-1));return MemorySeach(m, n);}long long MemorySeach(int m, int n) {auto llRet m_vW[m][n];if (-1 ! llRet) { return llRet; }llRet m_vW1[m][n];for (int h 1; h m; h) {MaxSelf(llRet, MemorySeach(h, n) MemorySeach(m - h, n));}for (int w 1; w n;w) {MaxSelf(llRet, MemorySeach(m,w) MemorySeach(m,n-w));}return llRet;}vectorvectorint m_vW1;vectorvectorlong long m_vW;
};VS自带的单元测试
templateclass T1,class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1 , t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i 0; i vv1.size(); i){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{int m, n;vectorvectorint prices;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){m 3, n 5, prices { {1,4,2},{2,2,7},{2,1,3} };auto res Solution().sellingWood(m, n, prices);AssertEx(19LL,res);}TEST_METHOD(TestMethod1){m 4, n 6, prices { {3,2,10},{1,4,2},{4,1,3} };auto res Solution().sellingWood(m, n, prices);AssertEx(32LL, res);}};
} 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
