D - National Railway
题意
??给定一个\(h\times w\)的数组，数组中\((i,j)\)位置上的值为\(a[i][j]\)，选定两个任意点\(s,t\)建立车站，需要的花费为\(a[s_i][s_j]+a[t_i][t_j]+c*(\mid s_i-t_i\mid+\mid s_j-t_j\mid)\)，试求所需最小花费。
思路
??由于是选定两个不同的点，所以我们可以将选点步骤分开，于是就可以把问题转化成从某一点出发，走了\(x\)步后在能到达的点建立另一个车站。
??现在考虑怎么移动我们的位置，由于每个点可以移动的方向有四个，如果对每个点都搜索，时间复杂度太高。可以发现，暴力搜索中存在大量的重复路径，所以我们从左上角开始搜索的时候，只搜索位于下方与左侧的点，从右上角开始的时候，搜索位于下方与右侧的点即可覆盖到所有的移动情况。
??所以我们可以用动态规划来解决本题。定义\(dp[i][j]:\)在已经建立一座车站情况下走到点\((i,j)\)所需的最小花费。对于只搜索下方与左侧的策略，能到点\((i,j)\)的方案是从点\((i-1,j)\)与点\((i,j-1)\)走一步过来，因此状态转移方程为\(dp[i][j]=min\left\{a[i][j],dp[i-1][j]+c,dp[i][j-1]+c \right\}\)。而搜索下方与右侧的策略的转移方程基本是一样的。
??此时我们得到的\(dp\)数组还没有加上建立另一个车站所需的花费，于是我们定义数组\(s[i][j]\)：在点\((i,j)\)上建立第二个车站所需的费用。由于我们前面已经计算过了建立一个车站和到任意点的费用，因此类似的，我们有状态转移方程\(s[i][j]=a[i][j]+c+min(dp[i-1][j],dp[i][j-1])\)。另一种搜索策略的转移方程是类似的。
??因此，我们只需要分别计算两种策略的\(dp\)数组和\(s\)数组，将\(s\)中的最小值输出就是我们要的结果
参考代码
点此展开
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1010;
const int INF=0x3f3f3f3f;
LL a[N][N];
LL f[N][N];
LL s[N][N];
int main()
{
LL h,w,c;
cin>>h>>w>>c;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
cin>>a[i][j];
//计算到下方与右侧
memset(f,0x3f,sizeof f);
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
f[i][j]=min(a[i][j],min(f[i-1][j]+c,f[i][j-1]+c));
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
{
s[i][j]=a[i][j]+c+min(f[i-1][j],f[i][j-1]);
}
LL res=s[1][1];
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
res=min(res,s[i][j]);
//计算到下方和左侧
memset(f,0x3f,sizeof f);
for(int i=1;i<=h;i++)
for(int j=w;j>=1;j--)
f[i][j]=min(a[i][j],min(f[i-1][j],f[i][j+1])+c);
for(int i=1;i<=h;i++)
for(int j=w;j>=1;j--)
res=min(res,a[i][j]+c+min(f[i-1][j],f[i][j+1]));
//其余情况和上述两种是重复的，因此只需要计算两种即可
cout<<res<<endl;
return 0;
}