状态机dp
需要细致划分状态，状态转移很像DFA的一种dp
状态机dp
基本概念
此处的状态机dp，特指那些状态转移时同一个阶段有很多种状态的dp。
举个例子，比如股票买卖中，同一个阶段就会有当前不持有股票，当前持有股票，当前刚出售股票处于冷却期这么几个状态。
在发现可以用dp解决某个题目的时候，如果发现按照起初的状态定义，在状态转移的时候发现转移的情况可以继续细分，就可以考虑加一维来区分同一阶段同一属性的不同状态。
这类问题的转移过程比其他的dp复杂一些，需要考虑全面状态与状态之间的关系。
几个例子
区间翻转最长非递减子序列
这也是前几年CF的一道原题（Round 462 div2 C）
题目大意
给你一个只有1和2组成的序列，长度在1e6之内，你可以至多选择任何一个区间做一次区间反转，问翻转（或者不翻转）之后的最长非递减子序列的长度最长是多少。
思路
不难发现一些性质：
- 题目中说数列中只有1和2这两种数字，所以最长非递减子序列一定是1....12....2这种二段式的，可以没有第一段或者第二段。
- 假设我们要翻转区间，那么，要是想要这次翻转有意义，那么最长非递减子序列中1和2的分界线应该出现在这个区间内部，否则的话不翻转也能统计得到相同的结果。
- 由上一条性质可以知道，1和2的分界线在中，那么在翻转之前，中应该取一个最长的2...21...1序列。所以在整个序列中，我们要找的是一个形如1...12....21....12....2的最长的子序列，或者说匹配出这么一个子序列。
当然，我们最后找到的最长的结果不一定包含上面那4段，比如假如不需要反转，中间两段中至少有一段是没有的。假设我们从左往右匹配，那么匹配阶段可以用以第i个字符结尾，以及当前匹配的子序列的结尾属于第j段（0 < j < 5）表示，即dp[i][j]。可以看出来相比于裸的最长非递减子序列，其状态定义多了一维，表示匹配阶段，这就可以看成是一个状态机dp了。
下面思考关键的状态转移：
- 1111...1状态，只可以由111...1状态转移过来
- 111..12...2状态，可以由111..1状态和111..12...2转移过来
- 111..12...21..1状态，可以由111...12...2状态和111..12...21...1转移过来
- 111..12...21..12..2状态，可以由111..12...21...1状态和11...12...21...12...2转移过来
故
if (a[i] == 1) {
dp[i][1] = dp[i - 1][1] + 1;
dp[i][2] = dp[i - 1][2];
dp[i][3] = max(dp[i - 1][2], dp[i - 1][3]) + 1;
dp[i][4] = dp[i - 1][4];
} else {
dp[i][1] = dp[i - 1][1];
dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + 1;
dp[i][3] = dp[i - 1][3];
dp[i][4] = max(dp[i - 1][3], dp[i - 1][4]) + 1;
}
初始化全部为0即可。最后的答案只要统计max(dp[n][3], dp[n][4])即可。
使用原地滚动数组优化的时候，注意状态刷新的顺序。不过略加观察可以发现这个问题无论以什么顺序刷新都能保证滚动数组的正确性。
其实这个题还有另一种做法：考虑到要求的是最长的1...12...21..12...2子序列，