数位DP

区间DP

树形DP和状压DP

区间DP和树形DP

区间DP, 就是以区间作为状态的DP
树形DP, 就是以子树作为状态的DP

区间DP的一般套路
dp[l][r] 表示从l到r的状态值

树形DP的一般套路
dp[u][辅助数] 表示以 u 为根节点的子树，满足条件的状态值。

典型例题:

day2 线段树, 树状数组

day 1 倍增 RMQ ST表 LCA

T1

题目描述

阿米巴和小强是好朋友。
阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮，他兴奋地叫个不停。而阿米巴则很淡定，他回想起曾经的那些日子，事业的起伏，情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来，简直什么都不算。
于是，这对好朋友不可避免地产生了分歧。为了论证自己的观点，小强建立了一个模型。他海面抽象成一个$1$到$N$的排列$P[1…N]$。定义波动强度等于相邻两项的差的绝对值的和，即：
$L = | P_2 - P_1 | + | P_3 - P_2 | + \cdots + | P_N - P_{N-1} |$
给你一个$N$和$M$，问：随机一个$1…N$的排列，它的波动强度不小于$M$的概率有多大？

答案请保留小数点后$K$位输出，四舍五入。

差分约束用于解决如下的一些约束的可行解：

分块思想，常用于处理区间问题，大概是把区间分为若干个块分别维护。

T1

https://www.luogu.com.cn/problem/P6850
纯模拟没啥可说.

T2

https://www.luogu.com.cn/problem/P6851

部分分：

1. c = 0
   胜负无关，那么可以直接做，每次取最大就行了

正解：

使用贪心，每次不能赢就放弃机会，能就选最省的。

T3

1. n, m <= 20
   使用暴力+奇怪数据结构可过.
2. val = 0
   区间差分排除法。
3. 正解
   合并区间，可以用线段树来标记。
   [l,r,val]相当于 l - r 里面有 0-val-1 却没有 val
   如此就可以很快合并。
   做完之后，就随便填就 ok 啦

T4

构造题。

1. 矩阵构造：
   
2. 面条构造
   
3. 三角构造
   画很多三角再连接就好了
4. 正解
   把路径看成点，车站看成边