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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *