AT_abc264_f [ABC264F] Monochromatic Path 题解

· · 题解

分析

若忽略操作，易知 DP。考虑操作带来的影响：

由于每次只会往右 / 下移动一格，影响当前格子颜色的操作只会有当前行 / 列的操作。故补充状态为 dp_{i,j,a,b} 表示 (1,1)\to(i,j)，行 i 是 / 否操作，列 j 是 / 否操作。

转移时，只需枚举上一格的状态，判断是否可以转移，统计好花费即可。

代码

#include<stdio.h>
#include<ctype.h>
#include<memory.h>
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2000;
namespace IO {
    const int bufsize = 230005;
    char gtchar()
    {
        static char buf[bufsize], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufsize, stdin), p1 == p2)? EOF: *p1++;
    }
    int read()
    {
        int ret = 0;
        char ch = gtchar();
        while(!isdigit(ch)) ch = gtchar();
        while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
        return ret;
    }
}using IO::read;
int n, m, r[maxn + 5], c[maxn + 5];
ll dp[maxn + 5][maxn + 5][2][2];
char ch, mp[maxn + 5][maxn + 5];
void chmn(ll &a, ll b) {if(b < a) a = b;}
ll min(ll &a, ll b) {return a > b? b: a;}
int main()
{
//  freopen("path.in", "r", stdin);
//  freopen("path.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; i++) r[i] = read();
    for(int i = 1; i <= m; i++) c[i] = read();
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++, ch = IO::gtchar())
        {
            while(!isdigit(ch)) ch = IO::gtchar();
            mp[i][j] = ch;
            if(i == 1 && j == 1)
            {
                dp[1][1][0][0] = 0;
                dp[1][1][0][1] = c[1];
                dp[1][1][1][0] = r[1];
                dp[1][1][1][1] = r[1] + c[1];
                continue;
            }
            for(int ii = 0; ii <= 1; ii++)
            {
                for(int jj = 0; jj <= 1; jj++)
                {
                    char t = mp[i][j] ^ ii ^ jj;
                    if(i > 1) chmn(dp[i][j][ii][jj], dp[i - 1][j][mp[i - 1][j] ^ jj ^ t][jj] + (ii? r[i]: 0));
                    if(j > 1) chmn(dp[i][j][ii][jj], dp[i][j - 1][ii][mp[i][j - 1] ^ ii ^ t] + (jj? c[j]: 0));
                }
            }
        }
    printf("%lld\n", min(dp[n][m][0][0], min(dp[n][m][0][1], min(dp[n][m][1][0], dp[n][m][1][1]))));
    return 0;
}