本文主要是介绍ABC210 D - National Railway，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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;
}

这篇关于ABC210 D - National Railway的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！