共 25 篇文章
法1：hash 思路 很简单的思路，用一个hash表，键为字符，值为一个pair，pair的first成员存字符的出现次数，second成员为该字符的下标，维护一个下标最小值为答案即可。 代码 ```cpp class Solution { public: int firstUniqChar(string s) { unordered_map> mp; for(int i = 0; i < s.size(); i++) { mp[s[i]].first++; mp[s[i]].second = i; } int pos = INT_MAX; for(auto el: mp) { if((el.second).first == 1) { pos = min(pos, (el.second).second); } } return …
传送门 题目描述 给定一个起始单词，一个目标单词与一个备选字典，通过以下规则将起始单词变到目标单词去： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 求最短变化步数。 思路 看到最短步数，首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树，于是思维转向如何建立图/树。 思路还是很清晰的：任何两个只差一个字母的单词之间可以连成一条无向边，所有的边共同构成整张单词图。建成图后再判断endWord是否在图中就行了。真正复杂的地方在实现。 单个的字符串并不好节点化，我们可以把每个单词映射为一个id值，然后用一个int的邻接矩阵来存储整个词图。 对于添加边的操作，朴素思路枚举每一对单词，判断它们之间是否可以存在一条边，如果是，则将其加入词图，但这样显然太慢了。 可以考虑构造间接节点。假设当前单词为hit，那么显然地，_it、h_t、hi_三个长相的单词都可以与hit连成一条边。那么我们只需要构造出这三个间接节点，然后将当前单词连在间接节点上就行了。不难得知，每一个可以与hit连边的单词都一定会连向这三个间接节点。 值得注意的是，这样的操作虽然节省了时间，但人为的增加了一些“不需要的边”。假设有两个相邻单词，他们原来可以直达彼此，现在需要通过间接节点来访问，所以说真实的步数应该等于当前步数/2。又因为初始化时会将beginWord也加入词图，所以最后的总步数还得额外的+1。 代码 ```cpp class Solution { public: unordered_map wordId; vector> mp; int idNum = 0; void addWord(string& str) { if(!wordId.count(str)) { wordId[str] = idNum++; mp.emplace_back(); } } void addEdge(string& …
传送门 题目大意 在一条只能前进后退的一维路径上，给定起点n与重点k，只有三种移动方式： 前进一步后退一步使坐标变为当前值的两倍 问走到终点最短需要几步。 思路 很经典的bfs板子题，直接bfs去枚举每一种走法。每次操作依次将三种移动方式计算所得的目标坐标放进队列，然后出队判断就行了。 代码 ```cpp #include #include #include #include using namespace std; const int LIM = 100000; queue que; bool vis[LIM + 10]; int steps[LIM + 10]; int bfs(int n, int k) { int now, next; que.push(n); …
传送门 题目大意 一个序列s，题目定义两种编码方式： 第一种方式是p，其中pi表示第i个右括号之前的左括号数；第二种是w，其中wi表示第i个右括号(包括它本身)之前完成匹配的括号对数。 现给出序列s在p方式下的编码，求出它在w方式下的编码序列。 思路 已知条件是p序列，那就从p序列入手。 对于pi，设j<i，那么pi-pj的含义显然是第j个右括号与第i个右括号之间的左括号数。而且不难得知，wi能达到的最大值就是i-j，因为括号能匹配成功的前提是有富余的右括号。那么按照这个逻辑去枚举每一对(i,j)就行了。 代码 ```cpp #include #include using namespace std; int t, n; int str[110]; int main() { cin >> t; while(t--) { cin >> n; for(int i = 0; i < n; i++) { scanf("%d", &str;[i]); int j = i - …
传送门 题目大意 给定一个由10种字符(p,q,r,s,t,N,K,A,C,E)组成的逻辑表达式，其中pqrst为逻辑变量，NKACE为逻辑运算符，他们的含义分别是 K==and：x && yN==not：!xA==or：x || yC==implies：(!x)||y E==equals：x==y 要求判断这个逻辑表达式是否为重言式，如果是就输出tautology，否则输出not 思路 根据题设，我们不难判断，单目运算符一定在整个字符串的后半部分，双目运算符一定在整个字符串的前半部分。例如ApNp，它应该被判为A(p,N(p))，所以上述结论的正确性是显然的。那么就可以像常规的表达式计算一样，从尾部压入栈，然后弹一个计算一个。 因为只有5个逻辑变量，所以最多只会有2^5=32种情况，依次枚举就好。 代码 我的写法 五重循环枚举每一位，最内层去枚举长度。 ```cpp #include #include #include #include using namespace std; string str; bool input(stack& sta, char ss, int p, int q, int r, int s, int t) …
传送门 题目大意 用2x1与2x2的小方块去填满一个2xn的长条形区域，问有多少种填法。 思路 很标准的dp。假设当前填到第i个位置，那么能继续往后推进的办法只有三种：竖着放一个2x1的方块，或者横着放两个2x1的方块、亦或者直接放一个2x2的方块。即，dp[n]的填法直接取决于dp[n-1]与dp[n-2]。 在n-1时只有一种方法可以填，所以dp[n-1]对dp[n]的贡献就是1*dp[n-1]；在n-2时有三种方法：竖着放俩、横着放俩、放块大的，因为“竖着放俩”的方法与n-1时重叠了，所以dp[n-2]对dp[n]的贡献就是dp[n-2]*2，最终得到转移方程： ```cpp dp[n] = dp[n-1] + dp[n-2] * 2; ``` 样例很善良的提醒了我们这题还是一个大数题目，所以用string来模拟大数加法，避免爆变量。 ```cpp string add(string a, string b) { //维护a长于b if(a.length() < b.length()) swap(a,b); //进位值 int up = 0; //自尾向头计算 for(int i = a.length() - 1, j = b.length() - 1; …
传送门 题目大意 一个学校有n(n<=50000)个学生，他们都可能信仰不同的宗教，你不能一个一个去问他们的信仰，但你可以通过询问得知两个学生的信仰是否一致，询问有m(m<=n*(n-1)/2)次。通过询问你可以知道校内学生的信仰总数上限，找到这个上限作为答案。 思路 其实就是一个并查集，题目翻译过来就是说给你一个图与它的一些边，找到所有的联通分量。 代码 ```cpp #include #include #include #include #include using namespace std; const int N = 55000; int cnt; int n, m; int dad[N]; void init(int top) { for(int i = 1; i <= top; i++) { …
传送门 冷知识：Y2K就是常说的千年虫。（这题的题意是真的搞，建议语文太差的人不要参与出题） 题目大意 微软公司每个月都可能盈余s元或者亏损d元，但具体是盈余还是亏损不知道。知道的是每连续的五个月统计一次总收入，都是亏损的(不难知道这样的统计一共有八次)。现问在这种条件下一年到头能盈利吗？如果能，找出最大盈利，如果不能就输出"Deficit"。 思路 这题抛开晦涩难懂的题干，其实挺简单的，两位数的数据范围，怎么都能过。有一种做法是统计出所有可能出现的盈亏情况，然后直接对sd判断就行了。 但我本着练算法的原则刷oj，肯定还是采用贪心的思路。 先假设每个月都是盈利的，然后对每个连着的五个月进行判断。如果满足题设的“亏损”条件，就挪到下一个连续的五个月继续判断；如果不满足，就将当前五个月中最后一个不亏损的月份置为亏损，继续上述操作。 代码 ```cpp #include #include #include using namespace std; int s, d; int arr[20]; int calcSum(int pos) { int res = 0; for(int i = pos; i < pos + 5; i++) res += arr[i]; …
传送门 题目大意 假设海岸是一条无限长的直线。陆地在海岸的一边，海洋在另一边。每个小岛都是位于海边的一个点。而任何位于海岸线上的雷达装置，只能覆盖d距离。所以如果小岛与一个雷达之间的距离最多为d，那么它可以被这个雷达覆盖。 我们使用笛卡尔坐标系，定义海岸是x轴，海边在x轴上方，陆地在下方。给定海洋中每个岛屿的位置，给定雷达装置覆盖的距离，你的任务是编写一个程序，找到覆盖所有岛屿的最小数量的雷达装置。请注意，岛屿的位置由其(x,y)坐标表示。如果无法完成覆盖，则输出“-1”。 思路 给定覆盖半径与一系列散点，问最少用多少雷达可以覆盖到所有小岛。 很明显是一个贪心问题。在思考贪心策略之前我们需要考虑一下输出“-1”的情况。首先，因为雷达只能装在岸边，所以如果至少存在一个点，它距岸边的距离大于雷达半径，显然就无法完成覆盖了。其次，数据中存在d<0的情况，这种情况也是输出-1. 接下来思考贪心。要让雷达尽可能少，那就要让每个雷达尽可能的多覆盖小岛。如何去判断多个小岛能否被同一个雷达覆盖就成了这道题的核心问题。 以每个岛屿为圆心，d为半径做一个新圆，圆与x轴相交的两点会构成一个区间。不难想到，如果任意两个岛屿的区间存在重合，那么它们就能被同一个雷达覆盖。 所以对每个岛屿计算出它的区间值，以左边界为关键字排序，然后去判断就行了。 代码 ```cpp #include #include #include #include #include #include #define PAIR pair using namespace std; const int N = 1010; int n, d, cnt; class Node { public: int …
传送门 经 典 老 番 最近算法课讲到递归，顺手写一点经典的回溯题来巩固基础。 回溯是一种通过枚举出所有可能情况来得到解答的算法，很直白也很经典。当确定当前情况不是解或不是最后一个解时，算法会逐步退回到之前的步骤，通过更改部分组成来枚举下一种情况。 放在这道题里，要得出n个数的全排列，不难得出它的递归思路，设cur为当前操作到的元素下标： cur==n，排列完了所有数，当前排列作为一个答案存储。cur<n，考虑第cur个位置填哪个数。这个数不能被用过，所以需要借助一个vis数组来判断。如果vis[nums[cur]]==0，那么可以填入当前数，填入后继续递归dfs(cur+1,n,nums)执行下一次操作。 回溯时会撤销这个被填入的数与标记，并尝试下一个数。 上述思路是回溯的基本想法，但就这题而言可以避免vis数组的使用，以节约少部分空间。 上述算法需要借助标记数组，是为了去判断当前数可否填入。 考虑一种新的做法，以cur为界，左边是已经执行过操作的数，右边是等待操作的数。为了维护这种结构，可以使用swap直接在nums数组上操作。 ```cpp class Solution { private: vector< vector > ans; void dfs(int cur, int len, vector& nums) { if(cur == len) { ans.push_back(nums); return; } for(int i = cur; i < len; i++) { …
传送门 题目大意 《飞行员兄弟：跟随条纹象》游戏中有一个任务，玩家需要打开一个冰箱。冰箱门上有16个把手。每个把手都可以处于两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才是打开的。手柄用矩阵4х4表示。你可以在任何位置(i,j)改变一个把手的状态(1≤i, j≤4)。然而，这也会同时改变第i行和第j列的所有手柄的状态。你的任务是找到打开冰箱所需的最小把手切换次数。 思路 与poj1753类似，每个格子只有0或1两种状态，那么只有奇数次的操作是有效地。结合题目4x4的小规模，考虑直接枚举答案。 接下来就是思考枚举方式。因为我们知道偶数次的操作等于没有操作，那么我们可以等效处理：在对(i,j)进行切换操作时，同时对同行列的把手也进行一次操作，那么整个过程等效为仅对(i,j)进行了一次有效操作。 [图片缺失] 原图：https://images0.cnblogs.com/i/470524/201407/281650033524598.png图源：https://www.cnblogs.com/Java-tp/p/3873557.html 参照上图，黄色区域的方格被操作了两次，等效为0次；红色区域的方格被操作了四次，等效为0次；黑色方格被操作了七次，等效为1次。 那么我们就得到了一个策略：在对某个方格(i,j)进行切换时，同时对同行列的方格也进行切换就能确保只改变(i,j)的状态。 那么我们只需要对所有"+"执行上述策略，并记录相关方格被操作的次数，最后在统计被操作数是奇数的方格就能得到所有有效操作。 代码 ```cpp #include #include using namespace std; int ans = 0; int cnt[5][5]; bool mp[5][5]; void switchOn(int x, int y) { for(int i = …
传送门 题目大意 Flip Game是在一个4x4的矩形棋盘上进行的游戏，16个方格中的每一个方格上都放置了有两面的棋子。每块棋子的一面是白色的，另一面是黑色的。每一轮你都要翻转3到5个棋子，从而将其上边的颜色从黑色变为白色，反之亦然。每轮要翻转的棋子按照以下规则选择。 1、在16枚棋子中任选一枚。 2、将所选棋子和所有相邻棋子向左、向右、向上、向下翻转（如果有的话）。游戏的目标是翻转所有棋子白面朝上或所有棋子黑面朝上。你要写一个程序，寻找实现这个目标所需的最少回合数。 思路 一个棋子有且仅有两个状态，非黑即白。所以，对同一颗棋子而言，翻动偶数次显然是没有意义的，只有奇数次的翻动才会改变棋子状态，所以只用考虑第一次翻面操作。一共十六个格子，最多16步就能全部翻完，所以从0~16枚举每个操作，只要某一次成功了，这次的步数就是最优的。 用dfs来翻，如果到叶子节点还没成功就回溯。需要注意的是回溯需要把之前翻过的所有棋子翻回来。 代码 ```cpp #include #include using namespace std; int ans; bool flag; bool mp[5][5] = {0}; //方向数组: //左、右、下、上、中 const int dx[5] = {-1, 1, 0, 0, 0}; const int dy[5] = {0, 0, -1, 1, …
这次要记录的是做leetbook：二叉树的经历，这是一本很小的book，所以决定用一晚上的时间做完。传送门 树的遍历 t1 二叉树的先序遍历 常规操作，简单题要做难，所以考虑用多种方法来写。 递归法 最常规的递归法，按照根->左->右的顺序来写就可以了。 ```cpp class Solution { public: void solve(TreeNode*root, vector& a) { if(root == NULL) return; a.push_back(root->val); solve(root->left, a); solve(root->right, a); } vector preorderTraversal(TreeNode* root) { vector ans; solve(root, ans); return ans; } }; ``` 迭代法 迭代法是用栈模拟递归的操作。因为栈具有先入后弹的特性，所以优先压右儿子进栈。 ```cpp class Solution …
LeetBook传送门 LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。 集合set的使用 t1两个数组的交集 求两个集合的交集，重复元素计算一次。 思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。 ```cpp class Solution { public: vector intersection(vector& nums1, vector& nums2) { setset1; setset2; vector ans; for(int i = 0; i < nums1.size(); i++) set1.insert(nums1[i]); for(int i = 0; i < nums2.size(); i++) set2.insert(nums2[i]); set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans)); return …
传送门 很经典的字符串问题。给定一个字符串，返回它最长且无重复字符的子串。 可以很直接的想到一个枚举的做法，两重循环遍历字符串去枚举子串，复杂度略小于O(n²)，但肯定会超时。于是想到滑动窗口。 滑动窗口可以在母串上维护一个检索区间，从而避免因为匹配失败而导致的低效下标回溯操作。 具体来说，如果窗口右端检索到一个重复字符，那么左端收缩，直到不存在重复字符位置。每次滑动结束后维护ans字符串即可。 ```cpp class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); int ans = -INT_MAX, left = 0; unordered_setstr; if(!n) return 0; for(int right = 0; right < n; right++) { while(str.find(s[right]) != str.end()) { str.erase(s[left]); left++; } …
动态规划是一个非常非常重要的算法。众所周知LeetCode周赛中十hard九dp，接触算法那么多年，动态规划始终没有做到完全的掌握，趁着这月LeetCode周赛的主题是dp，也争取完全掌握这门 算法。 内容会不定期更新，初步目标二十道，由易到难。 LeetCode-121:买卖股票的最佳时机 传送门 lc上的dp老题了，其实它只是借用了dp思想而已，和传统的dp有一点点差别。 首先考虑暴力做法。题意不难理解，找出数组中差值最大的两个数，输出他们的差值，要求较小数的下标要小于较大数。那么可以很简洁的写出一个直译： ```cpp class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int ans = 0; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) ans = max(prices[j]-prices[i], ans); return …
传送门 题目大意 如果通过插入 "+"和 "1 "可以从中得到一个形式完整的数学表达式，那么一个带括号的序列 就被称为正确。例如，"(())()"、"() "和"(()())) "等序列是正确的，而")("、"(()) "和"(()))("则不正确。 老师给德米特里的班级布置了一个非常奇怪的任务：她要求每个学生想出一个任意长度的序 列，只由开头和结尾的括号组成。之后，所有学生轮流说出自己想出的序列。轮到迪马时，他突然发现，所有同学都得到了正确的括号序列，而他是否得到了正确的括号序列，他不知道。 迪马现在怀疑自己只是漏掉了任务书中的 "正确 "二字，所以现在他想通过稍微修改自己的序 列来挽救局面。更准确地说，他可以任意次数（可能是零）地执行重排序操作。 重排序操作包括选择序列中任意一个连续的子串，然后以任意的方式对其中的所有字符进行重 排序。这种操作需要l纳秒，其中l是被重新排序的子段的长度。很容易看出，重新排序操作并 不会改变开括号和收括号的数量。例如对于"))(("，他可以选择子串")("，然后进行重排 序")()("(这个操作需要2纳秒)。 由于Dima很快就要回答，他想尽快让自己的序列正确。帮助他做到这一点，或者确定这是不可能的。 输入输出 输入 第一行包含一个整数n(1≤n≤10e6)表示序列的长度。 第二行包含长度为n的字符串，仅由字符"("和") "组成。 输出 打印一个整数：使序列正确的最小纳秒数，如果不可能做到，则打印"-1"。 难度不大的栈括号，遇到左括号就压进去，右括号弹，如果栈不空就输出-1，否则输出答案。 ```cpp #include using namespace std; typedef long long ll; …
题目大意：有n(n一定是偶数)堆硬币，他们的重量依次是21,22,...,2n。现在需要把他们分成两份，并让这两份硬币总质量之差的绝对值尽可能的小，请找到这个方案并输出质量之差的绝对值作为答案。 分法不难想， 将重量为2n的给第一份，重量为2n-1~2n-n/2-1的部分给第二份，剩下的再分给第一份。 原因很简单，2~ 2n 中 2n 大于其他n-1个数之和，所以先把 2n 拉出来单独放一堆，然后让另一堆的值尽可能大就行了。 观察答案： n=2,ans=2n=4,ans=6n=6,ans=14n=12,ans=30...... 不难得出上一个数*2+2就是下一个答案。 ```cpp #include using namespace std; typedef long long ll; int main() { int t; cin >> t; while(t--) { int n; cin >> n; ll k = 0; for(int i = 2; i <= …
传送门 二叉搜索树是一颗特殊的二叉树，它满足以下条件： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左右子树也都是二叉搜索树 显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。 但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左子树与右子树的高度差的绝对值小于等于1左右子树也都是平衡二叉搜索树 同时定义平衡因子为节点左子树与右子树深度之差。 那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), …
传送门 一个栈作为数据存储空间，另建一个辅助栈。每个入队的新元素就插入在存储栈的栈尾。每次删除就将存储栈里的元素依次弹出并压入辅助栈，操作结束后返回辅助栈栈顶元素作为答案，然后再依次将元素弹回存储栈。 ```cpp class CQueue { public: stack s1; stack s2; CQueue() { while (!s1.empty()) s1.pop(); while (!s2.empty()) s2.pop(); } void appendTail(int value) { s1.push(value); } int deleteHead() { if(s1.empty()) return -1; while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } int tmp = s2.top(); s2.pop(); while(!s2.empty()) { s1.push(s2.top()); …
传送门 题目要求在一个无序数组中找到第K大的元素，不能使用排序。 最开始的想法是借用冒泡的思想两重循环去枚举，但是显然会超时，于是想到了二叉堆。 题目要求输出第K大，那么只需要在原数组上构建一个二叉堆，然后执行k-1次删除操作，堆顶即使答案。 ```cpp class Solution { public: void update(vector& arr, int i, int maxSize) { int maxn = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left < …
传送门 这题很巧妙的。 题意是这样的：一个长度为n的nums数组，在自然状态下这个数组内的成员应该是(1,2,3,...,n)，但现在这个数组被打乱并拿走了一些数，我们要做的就是找出nums中缺失的第一个正数。 题目要求时间复杂度O(n)，空间复杂度O(1)。 这是一道hard，刚刚拿到手的时候挺懵的，在查阅大佬题解后了解到了一种“hash碰撞法”，以下做思路转述。 首先，合法的元素应该∈[1,n]，所以非正数成员直接标记为非法。第一次遍历，对于每个合法的成员，我们把它与自己位置上当前的元素做交换。第二次遍历去找出第一个与自己下标不相等的成员，答案就是这个下标。如果遍历到尾都没找到这样的成员，则答案为n+1。 上述思路的正确性是显然地，因为它严谨地把每一个成员放到自己应该在的下标上了，如果出现下标与值不等的情况，说明数组中缺失了这个成员。那么我们所找到的第一个缺失的成员自然就是符合题意的答案。 不难分析出这个算法的时间复杂度是线性的，也符合要求。 ```cpp class Solution { public: int firstMissingPositive(vector& nums) { for (int i = 0; i < nums.size(); i++) { if (nums[i] != i+1) { while (0 < nums[i] && nums[i] <= nums.size() && nums[nums[i]-1] …
传送门 思路：简单的链表去重，用一个set保存已有数据，每一步检测当前val是否出现过，未出现过就入集合，出现过就删除它。 ```cpp class Solution { public: ListNode* removeDuplicateNodes(ListNode* head) { if (head == nullptr) return head; unordered_set s = {head->val}; ListNode* p = head; while (p->next != nullptr) { ListNode* cur = p->next; if (!s.count(cur->val)) { s.insert(cur->val); p = p->next; } else { p->next …
传送门 LC的daily真是越来越骚了，本来打算写一个O(n3)T了后再来优化，结果居然过了，虽然击败感人... ```cpp //时间击败6.58% //空间击败7.14% class Solution { public: int threeSumClosest(vector& nums, int target) { int n = nums.size(); int minn = INT_MAX; int ans; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; …
传送门 题面 我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。 [图片缺失] 原图：http://lx.lanqiao.cn/RequireFile.do?fid=FaHtNHE3 输入 第一行两个数n和m，表示作品数和木板数；第二行n个数Hi，表示从左到右第i个作品的高度。 输出 一行一个数ans表示答案。 样例数据 样例输入 5 2 4 2 3 5 4 样例输出 22 数据规模 对于30%的数据：1<=n，m<=10；对于100%的数据：1<=n，m<=100，1<=Hi<=10000。 思路 题面意思转述一下就是：将若干幅矩形的画作通过不同的相邻组合方式，在用尽m块木板的情况下，使得覆盖它们的面积最小。显然这个面积由被覆盖区间中最高的画作来决定，所以需要设hmax[i][j]为hi~hj中画的最大高度。 设 dp[i][j]为用j块板子覆盖前i幅画的最小面积，记k为在dp[i][j]状态下还剩的板子数量。可以得到状态转移方程： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020031713184378-1024x61.png 关于初始状态的确定，这里在求最小值，所以dp初始化为INF。如果用一块板子来覆盖前i幅画，显然面积只能为i·hmax[1][i]，所以dp[i][1]初始化为 i·hmax[1][i] 。 ```cpp #include #include …