题解

第一次用深搜做，果不其然TLE了。
第二次看到只能向右或向下……呃呃呃我是朵拉吗这么大个字我都没看到
ok开始dp

#include <iostream>
#include <cstdio>
using namespace std;
char a[105][105];
long long dp[105][105];
long long n, m, k, z, x, y;
int main(){
	cin >> n >> m >> k >> z >> x >> y;
	for(int i = 1; i <= n; i++){
		cin >> a[i] + 1;
		for(int j = 1; j <= n; j++){
			dp[i][j] = -1e16;//不会负数memset，只能这样了
		}
	}
	if(a[x][y] == 'D') m += z;//如果降落在果实可以吃，不会被崩掉
	dp[x][y] = m;
	for(int i = x; i <= n; i++){
		for(int j = y; j <= n; j++){
			if(a[i][j] == 'M') dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]) - k);//是怪物，扣掉k格体力
			else if(a[i][j] == 'D') dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]) + z);//是果实，增加z格体力
			else dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]) - 1);//否则扣一格体力
		}
	}
	cout << dp[n][n];

	return 0;
}