洛谷：P3392：涂条纹

题目

P3392：涂条纹

分析

这是一个典型的动态规划的题目，不过有一些强制性的约束：首行必须是白色的，末行也一定是红色的。首行必须为白色（以及相应的变换的代价）可以作为DP的初始条件。

本题难点在于状态转换，需要考虑的点比较多。

我们用dp[i][j]表示第i行涂成某种颜色j的最低成本，用xxx_cost[...]表示当前行涂成某种颜色xxx的成本。

那么，对于某一特定的行i来说，它之前可能有几种情况：

1. 前一行为白色：意味着之前的i-1行也必须是白色。本行有两种做法：涂成白色，或者涂成蓝色。
   1. 如果涂成白色：很简单。就是前i-1行（都是白色）的成本加上本行涂成白色的成本：\(dp[i][WHITE]=dp[i-1][WHITE]+white\_cost[i]\)。¹
   2. 如果涂成蓝色：那么本行涂成蓝色的成本可以记作：\(dp[i][BLUE]\)，它应该是：之前i-1行都是白色的成本（\(dp[i-1][WHITE]\)）加上本行涂蓝的成本（\(blue\_cost[i]\)）,与下一步（2.1）得到的\(dp[i][BLUE]\)两者中较小的那个：\(dp[i][BLUE]=min(dp[i][BLUE], dp[i-1][WHITE] + blue\_cost[i])\)。
2. 前一行为蓝色：这意味着已经不能再出现白色了。本行有两种做法：涂成蓝色，或者涂成红色。
   1. 如果涂成蓝色：很简单。就是前i-1行（都是白色+蓝色，但i-1行必须是蓝色）的成本加上本行涂成蓝色的成本：\(dp[i][BLUE]=dp[i-1][BLUE]+blue\_cost[i]\)。
   2. 如果涂成红色：类似地，\(dp[i][RED] = min(dp[i][RED], dp[i - 1][BLUE] + red\_cost[i])\)。
3. 前一行为红色：这意味着不能再出现蓝色，只能出现红色。本行只有一种做法：涂成红色。
   1. 就是前i-1行（都是红色）的成本加上本行涂成红色的成本：\(dp[i][RED]=dp[i-1][RED]+red\_cost[i]\)，以及\(dp[i][RED]\)的较小值。

当然，这些状态的转换不是永远都能进行的。最直接的例子就是：白色不能直接接红色。我们需要用一些判定来避免这种情况。简单的方法，是将dp数组最初初始化取值就是一个大到不像话的数值——而通过动态规划的过程，这些数值是会不断降低的。

答案

思考

注意，上述提到的5中涂色情况，我是按照从第i行开始涂色，根据i-1行的涂色状况，确定本行的涂色状况。