1 条题解
-
0
#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
- 上传者