美团 - 最优规划
作者:
liweidong
,
2023-03-11 19:58:13
,
所有人可见
,
阅读 163
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, m, k;
string g[N];
int w[N][N];
int f[N][N];
const int MIN_INT = -0x3f3f3f3f;
int main(){
cin >> n >> m >> k;
for(int i=1;i<=n;i++){
cin >> g[i];
g[i] = " "+g[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin >> w[i][j];
}
int res = -1;
f[1][1] = 0;
for(int i=1;i<=n;i++) f[i][0] = MIN_INT;
for(int j=1;j<=m;j++) f[0][j] = MIN_INT;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char x = g[i][j];
int u = w[i][j];
char a = g[i][j-1];
char b = g[i-1][j];
if(x == a) f[i][j] = max(f[i][j-1]+u, f[i][j]);
else f[i][j] = max(f[i][j], f[i][j-1]+u-k);
if(x == b) f[i][j] = max(f[i-1][j]+u, f[i][j]);
else f[i][j] = max(f[i][j], f[i-1][j]+u-k);
res = max(res, f[i][j]);
}
}
cout<<res<<endl;
return 0;
}