介绍前言本题求最少准备时间 ⇔ 求排序后宽度数组的最长严格上升子序列长度。以下是小亦的详细讲解⬇️题目传送门https://www.luogu.com.cn/problem/P1233#解题思路步骤1、明确问题规则与核心1.1、给定n根木棍每根拥有长度l、宽度w及其加工木棍存在准备的时间规则第一根耗时了1分钟如果后一根木棍长、宽均≤前一根则无需额外准备否则加1分钟的准备是假并且要求求出加工全部木棍的最小总准备timing。1.2、该题可以通过Dilworth定理转换成经典的最长上升至序列问题。具体将木棍按照长度降序、同长度宽度降序并进行排序之后最小准备时间等价于宽度序列的最长严格上升至序列长度。1.3、本题不建议暴力枚举若暴力枚举所有排序进行模拟加工时间阶乘复杂度无法通过。2、问题转化以及逻辑推导2.2、题目给的问题等价于把所有木棍划分成尽可能少的递减序列。根据Dilworth定理最少划分链的数量最长反链长度。排序后反链对应宽度严格上升序列因此只需求出宽度序列最长上升子序列长度即可。3、动态dp状态设计我们仅需要一维dp数组去存储子问题答案不需要复杂图结构3.1、do[i]以排序后第i根木棍为结尾的最长严格上升宽度子序列长度。3.2、答案整个dp数组中的最大值就是最少的准备时间。##完成解题三步走小亦提供思维导图让大家更加清晰易懂###复杂度1、时间复杂度。2、空间复杂度。####代码#include iostream #include vector #include algorithm using namespace std; struct stick1 { int l, w; }; // 排序规则长度降序长度相等则宽度降序 bool cmp(const stick1 a, const stick1 b) { if (a.l ! b.l) return a.l b.l; return a.w b.w; } int main() { int n; cin n; vectorstick1 stick2(n); for (int i 0; i n; i) { cin stick2[i].l stick2[i].w; } sort(stick2.begin(), stick2.end(), cmp); vectorint w; for (auto s : stick2) { w.push_back(s.w); } // 求最长上升子序列 LIS vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (w[j] w[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } cout ans endl; return 0; }--- 感谢观看---制作Code.小亦代码提供Code.小亦题目思路部分提供无代码部分思路提供无知识共享无知识查找来源无初审Code.小亦。终审Code.小亦。本文章属于原创作品禁止任何人进行转载除合作之外如在阅读中发现知识性错误、代码错误、错别字错误等情况私信博主或评论或通过邮箱2952104443qq.com。另题目来源首页 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)特本文章/专栏在知乎网站合规授权发布。