[ABC264F] Monochromatic Path Solution

更好的阅读体验戳此进入

题面

给定一个 $H$$H$ 行 $W$$W$ 列的 $01$$01$ 矩阵。你可以花费 $R_i$$R_i$ 将矩阵第 $i$$i$ 行进行 $01$$01$ 反转，可以花费 $C_j$$C_j$ 将矩阵第 $j$$j$ 列进行 $01$$01$ 反转。你需要最小化花费，并使得从 $(1,1)$$(1, 1)$ 出发，只能向右或下走到达 $(H,W)$$(H, W)$ 至少有一条路径满足均为 $0$$0$ 或 $1$$1$。

Solution

首先不难想到每一行或一列最多进行一次反转操作，否则是无用的。发现只能向右或向下，则无后效性，故可以尝试 DP。

设 $dp(i,j,0/1,0/1)$$dp(i, j, 0/1, 0/1)$ 表示处理到第 $i$$i$ 行 $j$$j$ 列，第 $i$$i$ 行和第 $j$$j$ 列是否反转的最小花费。

我们设当前状态为 $dp(i,j,x,y)$$dp(i, j, x, y)$，令 $G_{i,j}$$G_{i, j}$ 表示矩阵的元素，则对于向下走的下一步的转移比较显然：

对于向右走的下一步也同理可得。

初始值即为 $dp(1,1,0,0)\leftarrow 0,dp(1,1,1,0)\leftarrow R_1,dp(1,1,0,1)\leftarrow C_1,dp(1,1,1,1)\leftarrow R_1+C_1$$dp(1, 1, 0, 0) \leftarrow 0, dp(1, 1, 1, 0) \leftarrow R_1, dp(1, 1, 0, 1) \leftarrow C_1, dp(1, 1, 1, 1) \leftarrow R_1 + C_1$。

最终答案即为 $min\{dp(H,W,x,y)\}$$\min\{dp(H, W, x, y)\}$。

Code

xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int H, W;
26
ll R[2100], C[2100];
27
ll dp[2100][2100][2][2];
28
bitset < 2100 > G[2100];
29

30
int main(){
31
    H = read(), W = read();
32
    for(int i = 1; i <= H; ++i)R[i] = read();
33
    for(int i = 1; i <= W; ++i)C[i] = read();
34
    for(int i = 1; i <= H; ++i)
35
        for(int j = 1; j <= W; ++j){
36
            char c = getchar(); while(!isdigit(c))c = getchar();
37
            G[i][j] = c == '1' ? true : false;
38
        }
39
    memset(dp, 0x3f, sizeof dp);
40
    dp[1][1][0][0] = 0, dp[1][1][1][0] = R[1], dp[1][1][0][1] = C[1], dp[1][1][1][1] = R[1] + C[1];
41
    for(int i = 1; i <= H; ++i)
42
        for(int j = 1; j <= W; ++j)
43
            for(int x = 0; x <= 1; ++x)
44
                for(int y = 0; y <= 1; ++y){
45
                    if((G[i][j] ^ x ^ y )== (G[i + 1][j] ^ y))dp[i + 1][j][0][y] = min(dp[i + 1][j][0][y], dp[i][j][x][y]);
46
                    else dp[i + 1][j][1][y] = min(dp[i + 1][j][1][y], dp[i][j][x][y] + R[i + 1]);
47
                    if((G[i][j] ^ x ^ y) == (G[i][j + 1] ^ x))dp[i][j + 1][x][0] = min(dp[i][j + 1][x][0], dp[i][j][x][y]);
48
                    else dp[i][j + 1][x][1] = min(dp[i][j + 1][x][1], dp[i][j][x][y] + C[j + 1]);
49
                }
50
    ll ans(LONG_LONG_MAX);
51
    for(int x = 0; x <= 1; ++x)for(int y = 0; y <= 1; ++y)ans = min(ans, dp[H][W][x][y]);
52
    printf("%lld\n", ans);
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

UPD

update-2023_01_03 初稿