hnust_zhouzisheng

分类

算法(3) 题解(27)

/ 注册

全部文章（共30篇）

【每日一题】粉刷匠

动态规划。原问题：n个木板粉刷t次的最多粉刷个数子问题：前i个木板刷j次的最多粉刷个数描述：记dp1[i][j]表示前i个木板刷j次的最多粉刷个数推出dp1[i][j]=max{dp1[i-1][j-k]+第i个板粉刷k次的最多粉刷个数},k<=j 这又产生了新问题，如何求某个板粉刷某次的最...

2020-06-10

0 998

【每日一题】失衡天平

动态规划。首先，题目说不限操作次数，但其实只要操作一次即可，因为每次操作得到的两堆重量差值均<=m，只要将每次得到的两堆按大小互补的方式与前一次的两堆合并到一起即可，最后相当于得到一次操作的结果。其次，动态规划。原问题：从n个物品中选出两堆重量差不超过m时最大重量和。子问题：从前i个物品选...

2020-06-10

2 876

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

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

2020-06-06

0 496

【题解】点对最大值

树上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 652

【算法】前向星存图

前向星是一种特殊的边集数组。不同于邻接表和邻接矩阵对顶点的处理，前向星存图处理的是边与边的关系。 int cnt; //记录边的编号 int head[maxn]; //head[u]表示上一个以u为起点的边的编号，初始化-1 struct st /...

2020-05-30

0 710

【每日一题】 Rinne Loves Edges

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

2020-05-18

0 537

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

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

2020-05-16

0 610

【每日一题】滑动窗口

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

2020-05-15

1 656

【每日一题】数学考试

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

2020-05-15

1 538

【每日一题】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 828