洛谷：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行的涂色状况，确定本行的涂色状况。

另外，本题也可以用暴力解决并AC。大致步骤如下：

1. 输入每一行的初始颜色，存入vector<string> grid(N)中。
2. 计算每一行涂成全白、全蓝、全红的费用。
3. 暴力枚举：假定总共有N ([0, N-1])行：
   1. 白色必然从第0行开始，到N-3行为止，留出至少一行涂蓝，一行涂红：for (int i = 0; i < N - 2; i++)
   2. 蓝色必然从i+1行开始，到N-2行为止，留出至少一行涂红：for (int j = i + 1; j < N - 1; j++)
   3. 累加[0, i]行涂白，[i+1, j]行涂蓝，[j+1, N-1]行涂红的费用。维持最小费用。
4. 输出最小费用。

#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;

    vector<string> grid(N);
    for (int i = 0; i < N; i++)
    {
        cin >> grid[i];
    }

    // 预计算：将每一行涂成特定颜色的成本
    vector<int> white_cost(N);
    vector<int> blue_cost(N);
    vector<int> red_cost(N);

    for (int i = 0; i < N; i++)
    {
        white_cost[i] = 0;
        blue_cost[i] = 0;
        red_cost[i] = 0;

        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] != 'W')
                white_cost[i]++;
            if (grid[i][j] != 'B')
                blue_cost[i]++;
            if (grid[i][j] != 'R')
                red_cost[i]++;
        }
    }

    int min_cost = INT_MAX;

    // 暴力枚举所有可能的分界线
    // i: 白色区域的最后一行（0-indexed）
    // j: 蓝色区域的最后一行（0-indexed）
    for (int i = 0; i < N - 2; i++)  // 白色至少1行，蓝色和红色各至少1行
    {
        for (int j = i + 1; j < N - 1; j++)  // 蓝色至少1行，红色至少1行
        {
            int cost = 0;

            // 计算白色区域成本：[0, i]
            for (int row = 0; row <= i; row++)
            {
                cost += white_cost[row];
            }

            // 计算蓝色区域成本：[i+1, j]
            for (int row = i + 1; row <= j; row++)
            {
                cost += blue_cost[row];
            }

            // 计算红色区域成本：[j+1, N-1]
            for (int row = j + 1; row < N; row++)
            {
                cost += red_cost[row];
            }

            min_cost = min(min_cost, cost);
        }
    }

    cout << min_cost << endl;

    return 0;
}

这个方法更直观，但时间复杂度为\(O(N^3)\)，而DP法只要\(O(N)\)即可。