题意

给你一个 $a$ 数组，其中 $a[i] = [startDay_i, endDay_i, value_i]$ ，表示第 $i$ 个会议在 $startDay_i$ 天开始，第 $endDay_i$ 天结束，如果你参加这个会议，你能得到价值 $value_i$ 。同时给你一个整数 $k$ 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和。$(k \in [1, n], k * n \in [1, 1e6], startDay_i, endDay_i \in [1, 1e9], value_i \in[1, 1e6])$

Solution

题目

给你两个单词 $a$ 和 $b$，请你计算出将 $a$ 转换成 $b$ 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

1. 插入一个字符

题目

从给定数列中能选出组成的最长等差数列长度为多少？$(n \in [1, 5000], a[i] \in [1, 1e9])$

Solution

$dp[i][j]$ 表示 $a[i]$ 为等差数列最后一个数，$a[j]$ 为倒数第二个数。

题意

在一维数轴上给出 $m$ 个线段，每个线段都都有 $l,r,w$ 三个数据代表这个线段的左右端点和这个区间权值。 从中取出若干个不相交的线段(区间端点可以共用)，在覆盖满 $[1,n]$ 的情况下，取出的线段中 $权重的最大值]$ 最小能为多少？

Solution

$dp[i]$ 代表覆盖满 $[1,i]$ 最大权值最小为多少，然后按左端点从小到大枚举线段，就有 $dp[r_i]=min(dp[r_i],max(dp[l_i],w_i))$。

题目1

体积和价值可能为负数的01背包。

Solution

逆向思维，对于体积为负的物品，我们可以一开始就装进去，背包对应的进行扩容，物品的体积和价值也对应取反。这样在进行背包dp 的时候就代表移除这个物品，答案取最大值即可。

题意

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

题目

构造一个长度为 $n$ 的序列，每个数字大小必须满足 $l <= a[i] <= r$，且和被 3 整除，问有多少种方法？

Solution

题目

给你两个队列$a$和$b$，问你能否构造出给定的队列$c$。

Solutuon

很经典的动态规划，$dp[i][j]$ 表示第一个队列的前 $i$ 个数和第二个队列的第 $j$ 个数能否组成第三个队列的前 $i+j$ 个数。状态转移方程：$dp[i][j] = (dp[i - 1][j]$ $and$ $a[i] == c[i + j]$ $or$ $dp[i][j - 1]$ $and$ $b[j] == c[i + j])$。

题目

求 $n$ 个节点，高度不超过 $h$ 的二叉树的个数，结果模 $1e9 + 7$。

Solution

题意

求二维最长上升子序列

Solution

对第一维进行从小到大排序，然后第二维从大到小排序，对第二维做LIS即可。