hnust_zhouzisheng

题解

算法(3)

/ 注册

全部文章 / 题解（共27篇）

【每日一题】德玛西亚万岁

状态压缩动态规划，即状压dp，是利用二进制表示状态的一种dp。根据题意，标记为1的土地只有有人(1)和无人(0)两种状态，所以状压显而易见。记dp[i][j]表示第i行状态为j的方案数，初始化dp[0][0]=1；同时采用二进制数ar[i]记录第i行的土地状态。首先，对于每一行i，状态j必须是合法...

2020-06-06

0 492

【题解】点对最大值

树上dp。记low1[u]为从u向下搜索到的最大路径值加起点值，low2[u]为从u向下搜索到的次大路径值加起点值。考虑非叶子节点u及以其为根的子树：若u为端点，则ans=max(ans,low1[u]+weight[u])；若u不为端点，则ans=max(ans,low1[u]+low2[u])。...

2020-06-01

1 646

【每日一题】 Rinne Loves Edges

题意：给定一棵带权树和它的根，要求删除一些边使得叶子节点无法到达根节点，求删除边的权值之和的最小值。思路：树型dp，其本质为搜索，即遍历树并在返回时维护相关的值。将原树拆分成以其孩子为根的多个子树，对于一棵子树有两种情况：1.删除子树的根与其双亲相连的边。2.删除子树的边。只要对这两种情况取最小值再...

2020-05-18

0 523

【每日一题】合并回文子串

题意：给定两个字符串a和b，从a和b中选取若干元素，不改变其在原字符串中的顺序，求能够形成的回文串的最大长度。思路：区间dp。用dp[i][j][k][l]表示从a串选取第i个到第j个元素，从b串选取第k个到第l个元素，这些元素能否形成回文串。可以这样考虑回文串的形成：一个回文串在两边加上相同的字符...

2020-05-16

0 603

【每日一题】滑动窗口

题意：给定一个长度为n的序列和长度为k的窗口，求每次窗口滑动时窗口内元素的最大值和最小值。思路：经典的单调队列题目，这里采用双端队列处理，维护单调非递增(/减)队列考虑求最小值：若ar[i]小于等于队尾元素，则不断弹出队尾元素，因为ar[i]比它们有更大的发展空间；将ar[i]入队，因为当队首元素不...

2020-05-15

1 648

【每日一题】数学考试

题意：给定一个长度为n的序列，选取两个不相交且长度为k的区间，求两个区间的元素之和的最大值。思路：记sum_right[i]为以i为右界且长度为k的区间内元素和，记left_max[i]为左界大于等于i的所有区间元素和的最大值。一趟遍历可求出sum_right，再利用其求出left_max，最后求得...

2020-05-15

1 537

【每日一题】tokitsukaze and Soldier

题意：有n个士兵，每个士兵 i 有武力值v[i]和限制人数s[i]，即：若选择了第 i 个士兵则选择的总人数不能超过s[i]。求v[i]总和的最大值。思路：贪心，优先队列。按s[i]从大到小的顺序进行排序并遍历，对于每项v[i]直接入队。若size<=s[i]直接更新ans；若size>...

2020-05-15

3 825