• 欢迎光临~

# [ABC264F] Monochromatic Path

### Problem Statement

We have a grid with \$H\$ rows and \$W\$ columns. Each square is painted either white or black. For each integer pair \$(i, j)\$ such that \$1 leq i leq H\$ and \$1 leq j leq W\$, the color of the square at the \$i\$-th row from the top and \$j\$-th column from the left (we simply denote this square by Square \$(i, j)\$) is represented by \$A_{i, j}\$. Square \$(i, j)\$ is white if \$A_{i, j} = 0\$, and black if \$A_{i, j} = 1\$.

You may perform the following operations any number of (possibly \$0\$) times in any order:

• Choose an integer \$i\$ such that \$1 leq i leq H\$, pay \$R_i\$ yen (the currency in Japan), and invert the color of each square in the \$i\$-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
• Choose an integer \$j\$ such that \$1 leq j leq W\$, pay \$C_j\$ yen, and invert the color of each square in the \$j\$-th column from the left in the grid.

Print the minimum total cost to satisfy the following condition:

• There exists a path from Square \$(1, 1)\$ to Square \$(H, W)\$ that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square \$(1, 1)\$ and Square \$(H, W)\$) have the same color.

We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.

### Constraints

• \$2 leq H, W leq 2000\$
• \$1 leq R_i leq 10^9\$
• \$1 leq C_j leq 10^9\$
• \$A_{i, j} in lbrace 0, 1rbrace\$
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

```\$H\$ \$W\$
\$R_1\$ \$R_2\$ \$ldots\$ \$R_H\$
\$C_1\$ \$C_2\$ \$ldots\$ \$C_W\$
\$A_{1, 1}A_{1, 2}ldots A_{1, W}\$
\$A_{2, 1}A_{2, 2}ldots A_{2, W}\$
\$vdots\$
\$A_{H, 1}A_{H, 2}ldots A_{H, W}\$
```

```3 4
4 3 5
2 6 7 4
0100
1011
1010
```

### Sample Output 1

```9
```

We denote a white square by `0` and a black square by `1`. On the initial grid, you can pay \$R_2 = 3\$ yen to invert the color of each square in the \$2\$-nd row from the top to make the grid:

```0100
0100
1010
```

Then, you can pay \$C_2 = 6\$ yen to invert the color of each square in the \$2\$-nd row from the left to make the grid:

```0000
0000
1110
```

Now, there exists a path from Square \$(1, 1)\$ to Square \$(3, 4)\$ such that all squares in the path have the same color (such as the path \$(1, 1) rightarrow (2, 1) rightarrow (2, 2) rightarrow (2, 3) rightarrow (2, 4) rightarrow (3, 4)\$). The total cost paid is \$3+6 = 9\$ yen, which is the minimum possible.

### Sample Input 2

```15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000
```

### Sample Output 2

```125
```

``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2005;
int h,w,r[N],c[N],a[N][N];
LL dp[N][N][2][2],ans;//0表示下，1表示右
LL dfs(int x,int y,int i,int j)
{
if(dp[x][y][i][j]!=-1)
return dp[x][y][i][j];
LL ret=1e18;
if(i)
{
int c=a[x][y]^j? ::c[y]:0;
if(x==h&&y==w)
return c;
if(y<w)
ret=min(ret,dfs(x,y+1,i,j)+c);
if(x<h)
{
if(a[x][y]^j)
ret=min(ret,dfs(x+1,y,0,1)+c);
else
ret=min(ret,dfs(x+1,y,0,0));
}
}
else
{
int c=a[x][y]^j? r[x]:0;
if(x==h&&y==w)
return c;
if(x<h)
ret=min(ret,dfs(x+1,y,i,j)+c);
if(y<w)
{
if(a[x][y]^j)
ret=min(ret,dfs(x,y+1,1,1)+c);
else
ret=min(ret,dfs(x,y+1,1,0));
}
}
//	printf("%d %d %d %d %lldn",x,y,i,j,ret);
return dp[x][y][i][j]=ret;
}
int main()
{
scanf("%d%d",&h,&w);
for(int i=1;i<=h;i++)
scanf("%d",r+i);
for(int i=1;i<=w;i++)
scanf("%d",c+i);
for(int i=1;i<=h;i++)
{
char ch;
for(int j=1;j<=w;j++)
scanf(" %c",&ch),a[i][j]=ch-'0';
}
memset(dp,-1,sizeof(dp));
ans=min(min(dfs(1,1,0,0),dfs(1,1,1,0)),min(dfs(1,1,0,1)+c[1],dfs(1,1,1,1)+r[1]));
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
a[i][j]^=1;
memset(dp,-1,sizeof(dp));
ans=min(ans,min(min(dfs(1,1,0,0),dfs(1,1,1,0)),min(dfs(1,1,0,1)+c[1],dfs(1,1,1,1)+r[1])));
printf("%lld",ans);
}
``````