区间DP
区间DP
例1. 关路灯
大意：给你初始位置$x_0$以及每个路灯的位置$x_i$和功率$p_i$，你的速度为1$m/s$，问关闭所有路灯后，最小的能耗
解：
规定$sum_k=\sum_{i=1}^{k}p_i$
设$dp[i][j][0/1]$表示关闭$[i,j]$的所有路灯后，你停留在i位置(0)或者j位置(1)的最小能耗
那么对于$dp[i][j][0/1]$有两种转移策略：
第一种策略：$dp[i][j]从dp[i + 1][j]$转移过来； 第二种策略：$dp[i][j]从dp[i][j+1]$转移过来
所以对于$dp[i][j][0]$，他只会从$dp[i+1][j][0],dp[i+1][j][1]$转移过来：
如果他从$dp[i+1][j][0]$转移过来，有：$dp[i][j][0]=dp[i+1][j][0]+(x_{i+1}-x_i)*(sum_{n}+sum_i-sum_j)$
如果他从$dp[i+1][j][1]$转移过来：有：$dp[i][j][0]=dp[i+1][j][1]+(x_j-x_i)*(sum_{n}+sum_i-sum_j)$
解释一下$sum_{n}+sum_i-sum_j$，因为我最后要站在i位置上，所以位置$[i+1,j]$的灯都是关上的，他们的功率和是$sum_j-sum_{i}$
所以剩下的在工作的功率就是$sum_n-sum_j+sum_i$
同理对于$dp[i][j][1]$，他只会从$dp[i][j-1][0],dp[i][j-1][1]$转移过来：
如果他从$dp[i][j-1][0]$转移过来，有：$dp[i][j][1]=dp[i][j-1][0]+(x_j-x_i)*(sum_n-sum_{j-1}+sum_{i-1})$
如果他从$dp[i][j-1][1]$转移过来，有：$dp[i][j][1]=dp[i][j-1][1]+(x_j-x_{j-1})*(sum_n-sum_{j-1}+sum_{i-1})$
解释一下$sum_n-sum_{j-1}+sum_{i-1}$，因为我最后要站在j位置上，所以位置$[i,j-1]$的灯都是关上的，他们的功率和是$sum_{j-1}-sum_{i-1}$，所以剩下的在工作的灯的总功率是$sum_n-sum_{j-1}+sum_{i-1}$
关于赋初值的问题，我们只需要吧初始位置$x_0$的dp设置为0即可，即$dp[x_0][x_0][0] = dp[x_0][x_0][1]=0$
其余的位置我可以不去管他，因为他是从i出发的
例2. 涂色
大意：给你一个长度为n的木板，涂成给定的颜色状态，其中对于相同的位置，先刷上的颜色会被后刷上的颜色覆盖，问最小的涂色次数
解：
我们设$dp[i][j]$表示把位置$[i,j]$涂成目标状态的最小涂色次数
那么，对于任意的i，有$dp[i][i]=1$，一个点，最小的次数一定是1
对于$i\ne j \land s[i]==s[j]$，那么$dp[i][j]=min(dp[i][j-1],dp[i+1][j])$
为什么？对于$dp[i][j-1]$，我在涂色$[i,j-1]$时，是可以把$s[i]$也考虑进来的($s[i]==s[j]$)，也就是说我可以先把$[i,j]$全部涂色成$s[i]$的颜色，之后再在$[i,j-1]$上找最优秀的涂色方式。
问题：把整个区间涂色之后不会导致我的$dp[i][j-1]$不成立吗？不会。因为先涂色的会被覆盖，刷的范围越大，只会对结果更有利
对于$i \ne j \land s[i]\ne s[j]$，那么$dp[i][j] = \max_{k=i}^{j}{dp[i][k]+dp[k+1][j]}$，就是两个区间的和
问题1：两个区间不会出现两者中间有连续一段相同的颜色，可以一步到位吗？会出现，但是我的k会枚举到他们分别在两个区域中的情况
问题2：会不会出现先把$[i,j]$都刷成某一种颜色，再进行涂色，使得方案更优？会出现，但是因为这里$s[i]\ne s[j]$所以当我的$k=i||k=j-1$时，实际上我的$dp[i][k]+dp[k+1][j]$就是问题2中描述的情况($dp[i][i] = dp[j][j]=1$)