[数据结构与算法]国家铁路（前缀和思想 + dp）

传送门

Solution

$ans=min(A_{x_1,y_1}+A_{x_2,y_2}+(|x_1?x_2|+|y_1?y_2|)\times C)$

1. $假设（x_1,y_1）位于左上角，（x_2,y_2）位于右下角$
   $ans=min(A_{x_1,y_1}?(x_1+y_1)\times C+A_{x_2,y_2}+(x_2+y_2)\times C)$
   $$\begin{gathered} 则可以利用二维前缀和的思想，求出 \\ min(A_{x_1,y_1}?(x_1+y_1)\times C),1\le x_1\le x_2,1\le y_1\le y_2 \end{gathered}$$

2. $$\begin{gathered} 则可以O（1）求出以（1，1）为左上角，（x_2,y_2）为右下角顶点的矩阵中的最小的ans了 \\ 然后枚举所有的点取最小值即可 \end{gathered}$$

3. $（x_1,y_1）位于左下角，（x_2,y_2）位于右上角，分析方法类似$

Code

const int N = 1e3 + 3;
ll a[N][N];
ll f[N][N];

int main()
{
	IOS;
	ll n, m, c; cin >> n >> m >> c;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	
	ll ans = 1e18;
	
	//左下到右上
	mt(f, 0x3f);//赋值无穷大
	for (int i = n; i >= 1; i--)
		for (int j = 1; j <= m; j++)
			f[i][j] = min(f[i + 1][j], f[i][j - 1]),
			f[i][j] = min(f[i][j],a[i][j] + (i - j) * c);
	for (int i = n; i >= 1; i--)
		for (int j = 1; j <= m; j++)
			ans = min(ans, min(f[i + 1][j], f[i][j - 1]) + a[i][j] + (j - i) * c);
	
	//左上到右下
	mt(f, 0x3f);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			f[i][j] = min(f[i - 1][j], f[i][j - 1]),
			f[i][j] = min(f[i][j], a[i][j] - (i + j) * c);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			ans = min(ans, min(f[i - 1][j], f[i][j - 1]) + a[i][j] + (i + j) * c);

	cout << ans << endl;

	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖