正经题解｜神庙大冒险

题意分析

在一个范围为$N \times N$的矩阵当中去求解如何从$S_x,S_y$前往终点$[N,N]$。 在这个矩阵当中会存在多种情况，一开始价值为$T$。

• 前往的坐标系所指向的类别为. ，价值-1。
• 前往的坐标系所指向的类别为M，价值-k
• 前往的坐标系所指向的类别为D，价值+z

针对于起点的类别不同采取

• 出现D的话进行+z的操作

方向只有右下

算法解析

根据前往的方向可以快速的求得状态和最基本的转移方程

设定$dp[i][j]$为到达坐标$[i,j]$的最大价值。

到达点$dp[i][j]$只能由上和左来到，也就是$dp[i][j] = max(dp[i-1][j],dp[i][j-1])$

然后，根据地图上的三种情况,MD来对于dp进行累加或者减少。

$IF$ $mp[i][j] = .$ $dp[i][j] = max(dp[i-1][j],dp[i][j-1]) - 1$

$IF$ $mp[i][j] = D$ $dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + z$

$IF$ $mp[i][j] = M$ $dp[i][j] = max(dp[i-1][j],dp[i][j-1]) - k$

我们设定$dp[S_x][S_y]$为初始状态，价值一开始为T，但是一旦$Mp[S_x][S_y] = D$ ，总价值需要加上z进行。

针对于状态转移方程书写代码即可。

时间复杂度分析

最坏需要遍历整个矩阵，所以时间复杂度为$O(n^2)$

STD标程

#include<bits/stdc++.h>
using namespace std;
bool vis[105][105];
long long answer ;
char mp[105][105];
long long dp[105][105];
long long n,t,k,z,sx,sy;
int main()
{
	int n;
	cin >> n >> t >> k >> z >> sx >> sy;
	for(int i = 1 ; i <= n ; i ++ ){
		for(int j = 1 ; j <= n ; j ++ ){
			cin >> mp[i][j];
		}
	} 
	dp[sx][sy] = t;
	if(mp[sx][sy] == 'D')dp[sx][sy] += z;
	for(int i = sx+1 ; i <= n ; i ++ ){
		dp[i][sy] = dp[i-1][sy];
		if(mp[i][sy] == 'D')dp[i][sy] += z;
		if(mp[i][sy] == '.')dp[i][sy] -= 1;
		if(mp[i][sy] == 'M')dp[i][sy] -= k;
	}
	for(int i = sy + 1 ; i <= n ; i ++ )
	{
		dp[sx][i] = dp[sx][i-1];
		if(mp[sx][i] == 'D')dp[sx][i] += z;
		if(mp[sx][i] == '.')dp[sx][i] -= 1;
		if(mp[sx][i] == 'M')dp[sx][i] -= k;
	}
	
	for(int i = sx + 1 ; i <= n ; i ++ )
	{
		for(int j = sy + 1 ; j <= n ; j ++ )
		{
			if(mp[i][j] == 'D')dp[i][j] += z;
			if(i==sx&&j==sy)continue; 
			dp[i][j] += max(dp[i-1][j],dp[i][j-1]);
			if(mp[i][j] == '.')dp[i][j] -= 1;
			if(mp[i][j] == 'M')dp[i][j] -= k;
			
		}
	}
	cout <<dp[n][n] << endl;
	return 0;
}