# 2. 题解

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

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

#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;
}