- 1 , 数状数组 (多与离散化算法相配套)
本质logn求和,logn修改
1,处理逆序问题 1)统计逆序对 2)统计v字形个数
2,以值域为横坐标，o(nlogn)在一维数组中，有多少个连续段满足和<t(离散化+前缀和+树状数组)
3,实时求出剩余的数中的第k小的数(树状数组+二分)
4,离线查询区间内不同数的个数 - 2,动态规划
从集合角度去考虑问题
1,背包问题 每一个物品具有代价和消耗，我们要算出在不同代价下的最大价值
2,从数组中选出k个长度为m的不相邻区间，求k个区间求和的最大值 f[i][j]表示已经选了i个数中，恰好选j段的最大值
3,最长公共序列，最长公共子串，最长上升子序列，最长上升子串
4,原序列中的每一个长度为k的连续子序列都至少包含一个被选中的元素，序列dp，每两个数中间距离<=k,从前i个数里面选了j个数，且第i个数被选
5,离散的区间覆盖问题，问最少可以考虑dp 如4421. 信号
6,连续长度为k的序列，之类的问题考虑二维dp
模板思路汇总
作者：
冷冷月光
,
2021-12-22 12:42:28
,
所有人可见
,
阅读 207
冷冷月光
,
2021-12-22 12:42:28
,
所有人可见
,
阅读 207
