线性dp
作者：
asukaqaqzz
,
2022-03-22 19:25:23
,
所有人可见
,
阅读 516
棋盘问题
子序列问题
| 题目 |
题意 |
分析/关键字 |
题解 |
| 895.最长上升子序列 |
给一个长度为N的数列,求严格单调递增的子序列的最大长度 |
模板题 |
|
| 896.最长上升子序列 |
给定一个长度为N的数列,求最长上升子序列长度,1<x<100000 |
二分,队列 |
题解 |
| 1017. 怪盗基德的滑翔翼 |
只能往一个方向跑,且下一次只能跳到比当前矮的位置,求最多跳跃数 |
lis,lds |
|
| 1014.登山 |
给定长度为n的数列,一旦开始下山只能走海拔更低的点,求上山下山这个过程中最多经过的点数 |
lis,lds |
|
| 482.合唱队列 |
N 位同学站成一排，音乐老师要请其中的 (N−K) 位同学出列，使得剩下的 K 位同学排成合唱队形。 合唱队列是一个单调递增又递减的队伍 |
lis,lds |
|
| 1012.友好城市 |
有n个友好城市对,求航线不相交最多可行友好城市 |
lis,贪心 |
题解 |
| 1016.最大上升子序列和 |
给定一个长度为n的数列,求最大上升子序列的和 |
lis |
|
| 1010.拦截导弹 |
有n个导弹,导弹系统每次只能拦截不高于之前拦截的高度的导弹,求最多能拦截导弹数,和需要的系统数 |
lis,lds,贪心,二分 |
题解 |
| 187.导弹防御系统 |
每个系统要么一直上升,要么一直下降,求至少多少套防御系统,能够把他们全部击落 |
搜索,贪心,剪枝 |
题解 |
| 314.低买 |
求一个最长下降子序列,并求最长下降子序列个数(子序列元素有一个不同,则整个子序列不同) |
lis,方案数 |
题解 |
多序列问题
线性dp
| 题目 |
题意 |
分析/关键字 |
题解 |
| 271.杨老师的照相排列 |
有n个学生合影,站成左端对齐的k排,每排指定人数且左到右身高递减,每一列后到前身高递减,求多少种安排合影位置的方案 |
线性dp,结论,打表 |
题解 |
| 273.分级 |
给定长度为N的序列A，构建一个长度为N的序列B，满足B非严格单调, |
Ai-Bi |
的和最大 |
| 4378. 选取数对 |
选取k个大小为m不重叠的区间,求区间和最大值 |
动态规划优化,背包问题 |
题解 |
| 312.乌龟棋 |
有n个格子,每个格子都有分数,m张卡片,每张只能用一次,求最大分数和 |
线性dp,记录状态 |
|
| 274.移动服务 |
有3名员工分为在1,2,3,给出一组请求,每次员工移动需要花费,求最小花费 |
dp的优化,刷表法,线性dp,记录状态 |
题解 |
输出方案
| 题目 |
题意 |
分析/关键字 |
题解 |
| 315. 旅行 |
寻找a,b所有可能的最长公共子序列,并输出 |
输出方案,搜索,前缀和 |
题解 |
| 313.花店橱窗 |
输出最大美观程度和的值,并输出对应方案 |
输出方案,dp |
题解 |
| 926.免费馅饼 |
可以左右移动-2，-1,0,1,2,求获得的最大馅饼分数,并求每次移动决策 |
输出方案,dp |
题解 |
