1 条题解

  • 0
    @ 2025-9-21 8:56:57

    #include <stdio.h> #include <string.h> #include <limits.h>

    int min(int a, int b) { return a < b ? a : b; }

    int main() { int n, m; scanf("%d %d", &n, &m); char grid[45][55]; for (int i = 0; i < n; i++) { scanf("%s", grid[i]); }

    int costW[45], costB[45], costR[45];
    for (int i = 0; i < n; i++) {
        int w = 0, b = 0, r = 0;
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'W') w++;
            else if (grid[i][j] == 'B') b++;
            else r++;
        }
        costW[i] = m - w;
        costB[i] = m - b;
        costR[i] = m - r;
    }
    
    int dp[45][3];
    dp[0][0] = costW[0];
    dp[0][1] = INT_MAX;
    dp[0][2] = INT_MAX;
    
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i-1][0] + costW[i];
        if (dp[i-1][0] < INT_MAX && dp[i-1][1] < INT_MAX)
            dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + costB[i];
        else if (dp[i-1][0] < INT_MAX)
            dp[i][1] = dp[i-1][0] + costB[i];
        else
            dp[i][1] = INT_MAX;
            
        if (dp[i-1][1] < INT_MAX && dp[i-1][2] < INT_MAX)
            dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + costR[i];
        else if (dp[i-1][1] < INT_MAX)
            dp[i][2] = dp[i-1][1] + costR[i];
        else
            dp[i][2] = INT_MAX;
    }
    
    printf("%d\n", dp[n-1][2]);
    return 0;
    

    } INT_MAX换成足够大的数也是可以的

    • 1

    信息

    ID
    595
    时间
    1000ms
    内存
    64MiB
    难度
    9
    标签
    递交数
    12
    已通过
    3
    上传者