区间DP
洛谷P3147Problem
定义 \(f[i][j]\) 存储从左端点 \(j\) 开始，能合并出 \(i\) 的右端点位置，将其设为 \(k\) 。
下面我们推转移方程。从题意可以看出，两个相邻的 \(i-1\) 能够合并出 \(i\) 。那么在 \(f[i][j]\) 后所对应的就是 \(f[i][k]\)，这两个 \(i\)合并能够得到一个\(i-1\)，左端点是 \(j\) ，右端点是新得到的 \(f[i+1][j]\) 。
初始化时，对于每一个 \(a[i]\) ，能够合并出其本身(实际上并不需要合并)的右端点只需要+1即可，即
线性DP
CF edu182CProblem
定义 \(dp[i][j]\) 为对于第 \(i\) 组是否交换(其中 \(j\) 的数只能为0/1，分别对应不交换和交换)，转移方程分为两种情况：
-
\(a[i] \geq a[i-1]\) and \(b[i] \geq b[i-1]\) (即本次不需要交换)
\[dp[i][1] = (dp[i][1]+dp[i-1][1]), dp[i][0] = (dp[i][0]+dp[i-1][0]) \] -
\(a[i] \geq b[i-1]\) and \(b[i] \geq a[i-1]\) (本次交换)
\[dp[i][1] = (dp[i][1]+dp[i-1][0]), dp[i][0] = (dp[i][0]+dp[i-1][1]) \]
AT abc404EProblem
定义 \(dp[i]\) 为将从 \(i+1\) 开始所有的石子分到当前点的最少步数。很容易想到，我们对 \(dp\) 数组设置一个极大值，并且对最后一个 \(a[i]\) 不为0的点开始往后的 \(dp\) 数组全部设为0(显然的，这些地方无法被转移到且不需要被转移到)作为预处理。
对 位置 \(i\) 倒序枚举。对每个位置 \(i\) 所对应的可转移范围 \([max(0,i-c[i]), i-1]\) ，用 \(j\) 表示，很显然的能够想到：
同时，很容易忽略的一点在于：该点往前移的范围仅限于到该点前的第一个\(a[i] = 1\)的位置 \(i\) 。根据贪心思想，将当前点的所有点转移到同一个\(1\)的身上显然是更优的(转移次数变小)，但是，如果在上述边界后继续转移，之后的贡献将会和该点前的第一个\(a[i] = 1\)的位置 \(i\) 两者贡献起冲突，故代码中存在：
for(int i = n-1;i > 0; i--){
for(int j = i-1;j >= max(0ll,i-c[i]); j--){
dp[j] = min(dp[j],dp[i]+1);
if(a[j]) break;//这一步用来判断边界
}
}