1. 题面

传送门=￣ω￣=

2. 题解

让我们红尘作伴，一起刷刷水题。。。

$f[i][j][k][l]$表示当前在第 $i$块木板的第 $j$个位置，还剩下 $k$次染色机 (ji) 会 (fei)，上次染色颜色为 $l$

转移就是枚举这一位是否填新的颜色，如果填色则 $k–$，然后枚举填什么颜色。

如果不填色就沿用之前的颜色。

很显然所有格子填色的方案中一定包含了最优方案。

复杂度就是 $O(n ^ 2 \times T)$的了。

（用记忆化搜索实现更加愉♂悦）

代码：

#include <bits/stdc++.h>

#define NS (55)
#define TS (2505)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, T, f[NS][NS][TS][2];

char col[NS][NS];

int Dfs(int a, int b, int k, bool c)
{
    if (a > n) return 0;
    int& F = f[a][b][k][c];
    if (F != -1) return F;
    F = 0;
    int na = a, nb = b + 1;
    if (b == m) na = a + 1, nb = 1;
    if (b != 1)
    {
        if (col[a][b] - '0' == c) F = max(F, 1 + Dfs(na, nb, k, c));
        else F = max(F, Dfs(na, nb, k, c));
    }
    if (k > 0)
    {
        if (col[a][b] == '0') F = max(F, 1 + Dfs(na, nb, k - 1, 0));
        else F = max(F, Dfs(na, nb, k - 1, 0));
        if (col[a][b] == '1') F = max(F, 1 + Dfs(na, nb, k - 1, 1));
        else F = max(F, Dfs(na, nb, k - 1, 1));
    }
    return F;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(T), memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; i += 1) scanf("%s", col[i] + 1);
    printf("%d\n", Dfs(1, 1, T, 0));
    return 0;
}