DP再次总结

## 1. 状态
​ 区间$DP$的状态一般 设 f[l][r] 表示区间 [l][r] ....。但有些时候可以直接设 $f_i$ 表示 $[1,i]$…。
​
​ 转移的时候会依靠断点，即 $f[l][r]=min/max${$f[l][k]+f[k+1][r]$}。
​
​ 常见的优化有两种 :

​ 四边形不等式

​ 递推

2.例题

1. 表达式的亿种可能性

   直接算是不行的，我们要去乘上每一个数的代价。

   原因是 加法和减法可以交换顺序。

   eg. : $(1+1)+2\ =\ 1+(1+2)$

   乘法具有分配率。

2. 有味道的数字

   爆搜发现 $max\ ans\ =\ 11$ , 且 $当且仅当\ n=3\ 或\ n=7\ $ 时，$ans=-1$。

   用 $f[i]\ (f:vector)$ 存 $ans_n\ =\ i$ 的 $n$。

3. 守卫

   题目具有迷惑性，容易想成单调栈。

   但发现加入点后需要一段区间的信息。

   所以直接区间 $DP$。

   枚举 $r$ , $l\ =\ r\ \rightarrow\ 1$，递推。

4. 祖玛游戏 && 单调栈

   打不过 (二维状态表示不完全) 就加入 (把表示不完全的信息加入状态)。

   实在不行还能加辅助数组。

   如果循环有后效性，或者循环讨论复杂，用 $dfs$。

   思想来源于二分 ： 把原问题转换为可行性问题

5. 括号序列

   算重了怎么办？ 学习 $Catalan$ ！

   我们知道

   $C_{n+1}=C_0C_n+C_1C_{n-1}+C_2C_{n-2}+...+C_{n-1}C_1+C_nC_0\ (注意这里没有重复)$

   同理 ,

---

---

3. 好题

1. HDU - 2476

   (空 -> B) - (A -> B)

2. CodeForces - 149D

   高维状态 ：

   $f_{l,r,x,y}$ 表示 区间$[l,r]$中，左端点是$x$,右端点是$y$的方案数。(左右端点均hash过)。

3. 262144 P

   状态不同于普通区间$DP$，类倍增，设的是

   $f_{i,k}\ 表示\ 从\ i\ 开始直到合出\ k\ 所需的最小长度。$

---

4.总结

状态的根本问题是 : 如何用最简洁的信息使得答案能够被(不重复)，不遗漏的算出来。

即使是 $f_{l,r}$ 也是逃不过的。

区间 $DP$ 一般满足 一些局部最优解能凑出全局最优解，不行的话就得加维度。