T4 龙傲天の纪念

题目背景

为了祭念上次膜你赛的失败，也为了纪念诚心诚意帮龙傲天纠错的同学们，龙傲天又出了一道水题放T4供大家AK比赛。

题目描述

在龙傲天 $1145$ 平方米的客厅里有一块 $n\times m$ 的地毯，地毯上有 $n\times m$ 个网格，每个网格要么是黑色的，要么是白色的。

忙碌了一天刚回到家的龙傲天要从客厅西北方的大门到东南方的撤硕打崩铁(?) 可是顽皮的sKeLlA-早已在此等候多时，他霸占了龙傲天客厅里的地毯(??)要求龙傲天必须走在颜色一样的格子上。

倘若龙傲天绕道而行或者乱走，凶狠的sKeLlA-就会把龙傲天活活肘死(???)。龙傲天可以给 sKeLiA- $r_i$ 大洋把第 $i$ 行白格子涂黑，黑格子涂白；也可以给 $c_j$ 大洋把第 $j$ 列的白格子涂黑，黑格子涂白。

由于龙傲天的脑子已经是崩铁的形状了，所以请你求出使得地毯中存在一条从 $(1, 1)$ 到 $(n, m)$ 的路径（只能向下或向右走）且路径上的颜色全为黑或全为白的最小花费。

输入格式

第一行两个整数 $n$ , $m$ 如题意所示。

接下来一行 $n$ 个整数 $r_i$ 如题意所示。

接下来一行 $m$ 个整数 $c_j$ 如题意所示。

接下来 $n$ 行每行 $m$ 个数为网格图上每个格子的颜色，其中1为黑色，0为白色。

输出格式

一行一个整数表示最小代价。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #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

样例输出 #2

提示

对于 $20\%$ 的数据： $n,m\leq 10$ ， $1\leq r_i,c_j\leq 10$ 。

对于 $40\%$ 的数据： $n,m\leq 100$ ， $1\leq r_i,c_j\leq 10^2$ 。

对于 $60\%$ 的数据： $n,m\leq 500$ ， $1\leq r_i,c_j\leq 10^4$ 。

对于 $80\%$ 的数据： $n,m\leq 1000$ ， $1\leq r_i,c_j\leq 10^6$ 。

对于 $100\%$ 的数据： $2\leq n,m\leq 2000$ ， $1\leq r_i,c_j\leq 10^9$ ， $A_{i,j}\in\lbrace 0,1\rbrace$ 。

样例解释

对于样例1中的网格，可以对第 $2$ 行和第 $2$ 列进行 $1$ 次操作，原图变成：

0000
0000
1110

代价为 $9$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,r[2002],c[2002];
char a[2002][2002];
int dp[2002][2002][2][2];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>r[i];
	for(int i=1;i<=m;i++)
		cin>>c[i];
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
	}
	memset(dp,0x3f,sizeof dp);
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			dp[1][1][i][j]=i*r[1]+j*c[1]; 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1) continue;
			for(int p=0;p<2;p++) for(int q=0;q<2;q++)
			for(int u=0;u<2;u++) for(int v=0;v<2;v++){
				if(q==v&&(a[i][j]^p)==(a[i-1][j]^u)){
					dp[i][j][p][q]=min(dp[i][j][q][v],dp[i-1][j][u][v]+p*r[i]);
				}
				else if(p==u&&(a[i][j]^q)==(a[i][j-1]^v)){
					dp[i][j][p][u]=min(dp[i][j][p][q],dp[i][j-1][u][v]+q*c[j]);
				}
				
			}
		}
	}
	int ans=0x3f3f3f3f3f3f3f3f;
	for(int i=0;i<2;i++){
		for(int j=0;i<2;j++){
			ans=min(dp[n][m][i][j],ans);
		}
	}
	cout<<ans;
	return 0;
}

2025/1/17 17:00