National Railway 题解(at_abc210 D 动态规划)

National Railway 题解[at_abc210 D 动态规划]

• 题目：National Railway
• 解析
• 参考源码

题目：National Railway

地址：atcoder_abc210_d

解析

• TAG: DP
• DESCRIPITION:

H×W的地图上建俩个站点，地图上每一个坐标（i，j）都有一个权重A[i,j]，整个地图有一个参数C表示每一单位路径的权重。
现在要建造俩个站点连通俩个点，需要耗费cost值为A[i1,j1]+A[i2,j2]+n*C,n为俩个点间的距离（i2-i1+j2-j1）

• INPUT:
  

• SOLUTION:

  1. HW的范围决定了这道题不能暴力，而且很明显这应该具有最优子结构性质，也就是能用动态规划dp做。但要建立俩个点，所以想要一下子把答案dp出来经过思考后发现不大现实，那我们就先来一个点进行dp。
  2. 建立dp1[][]二维数组，dp1[i,j]表示i，j划定范围内建立一个点并且拓展到i，j位置后产生的最小费用值，而拓展方向就是两个建立点的连线方向，也就是斜上和斜下，我们都要去求解，但逻辑一样所以假定现在要求斜下方向。那么 ：

dp1[i][j] = min(A[i][j],dp1[i-1][j]+C,dp1[i][j-1]+C) .

  3. 对于斜下方向，我们有了建立了第一个点后的具体最小费用情况dp1，那我们再建立dp2表示ij位置建立第二个点的最小花费值：

dp2[i][j]=min(dp1[i-1][j],dp1[i][j+1])+C+A[i][j]

，其中的最小值就是斜下方向情况下的答案。（其实求dp2并不算是动态规划了，但取名作dp就不改啦）
  4. 这里不要忘记了要类似地再去求斜上方向下的最小值，最后得到最终解。

参考源码

#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 1e3;
const ll INF = 1e18;
ll A[MAXN+5][MAXN+5];
ll dp1[MAXN+5][MAXN+5]; // 该位置左上方区域（或case2 右上方区域）内一个站点建好，并且走到了这个点的cost 
ll dp2[MAXN+5][MAXN+5]; // 该位置建立第二个点的总cost 
int main()
{ios::sync_with_stdio(false);ll H,W,C;// inputcin>>H>>W>>C;for(int i=1;i<=H;i++){for(int j=1;j<=W;j++){cin>>A[i][j];}}// dp initializefor(int i=1;i<=H;i++){dp1[i][0]=INF;dp1[i][W+1]=INF;}for(int j=1;j<=W;j++){dp1[0][j]=INF;}// dp1 for case1for(int i=1;i<=H;i++){for(int j=1;j<=W;j++){long long minn = A[i][j];if(dp1[i-1][j]+C<minn){minn = dp1[i-1][j]+C;}if(dp1[i][j-1]+C<minn){minn = dp1[i][j-1]+C;}dp1[i][j]=minn;}}long long minAns = INF;// dp2 for case2for(int i=1;i<=H;i++){for(int j=1;j<=W;j++){dp2[i][j] = min(dp1[i-1][j],dp1[i][j-1])+C+A[i][j];minAns = min(minAns,dp2[i][j]);}}	// dp1 for case2for(int i=1;i<=H;i++){for(int j=W;j>=1;j--){long long minn = A[i][j];if(dp1[i-1][j]+C<minn){minn = dp1[i-1][j]+C;}if(dp1[i][j+1]+C<minn){minn = dp1[i][j+1]+C;}dp1[i][j]=minn;}}// dp2 for case2for(int i=1;i<=H;i++){for(int j=W;j>=1;j--){dp2[i][j] = min(dp1[i-1][j],dp1[i][j+1])+C+A[i][j];minAns = min(minAns,dp2[i][j]);}}	cout<<minAns<<endl;return 0;	
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！