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

上一篇:外观模式(c++实现)


下一篇:c 20210706