牛客2019 East Central North America 部分题解

本文主要是介绍牛客2019 East Central North America 部分题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客题目地址

E Just Passing Through

方法：用dp[i][j][k]表示在这个地点（包括自己）经过k个pass所经过的最小高度和。
首先用is_pass[i][j]来记录一个地方是不是pass，注意在判断pass的时候四周不能有-1，自己也不能为-1，训练时因为这个导致一直WA。

然后第一行和最后一行要单独处理，因为只有两个点能到达。

状态方程为:(伪代码)

if(location[i][j] is pass)
dp[i][j][k+1]=min{dp[i][j][k+1], dp[i+1][j-1][k]+h[i][j], dp[i][j-1][k]+h[i][j], dp[i-1][j-1][k]+h[i][j]}
else
dp[i][j][k]=min{dp[i][j][k], dp[i+1][j-1][k]+h[i][j], dp[i][j-1][k]+h[i][j], dp[i-1][j-1][k]+h[i][j]}

#include <iostream>
#include <string.h>
#define mem(a, n) memset(a, n, sizeof(a))
using namespace std;
long long inf=99999999;
int loc[505][505];//表示该点高度
int is_pass[505][505];//记录该点是否为pass
long long dp[505][505][12]; //dp[i][j][k]表示第i行第j列经过k个pass的最小高度差和int main()
{int r, c, n;long long ans = inf;cin>>r>>c>>n;getchar();for (int i = 1; i <= r; i++){for (int j = 1; j <= c; j++){cin>>loc[i][j];}}mem(is_pass, 0);//dp初始化为无穷大for (int i = 0; i <=r+1 ; i++)for (int j = 0; j <=c+1; j++)for (int k = 0; k < 12; k++)dp[i][j][k] = inf;//最西边初始化for (int i = 1; i <=r; i++){if (loc[i][1] != -1){dp[i][1][0] = loc[i][1];}}//判断一个位置是不是passfor (int i = 2; i < r; i++){for (int j = 2; j < c; j++){//注意！！！！四周和自己不能是-1if(loc[i][j]==-1||loc[i][j-1]==-1||loc[i][j + 1]==-1||loc[i + 1][j]==-1||loc[i - 1][j]==-1) continue;int pass = loc[i][j];if (pass > loc[i][j-1] && pass > loc[i][j + 1] && pass < loc[i + 1][j] && pass < loc[i - 1][j]){is_pass[i][j] = 1;}}}//从左到右遍历for (int j = 2; j <= c; j++){int pass, jj = j - 1;//第一行，第一行和最后一行不存在passif (loc[1][j] != -1){//pass数量for (int k = 0; k < 11; k++){if (loc[1][jj] != -1)dp[1][j][k] = min(dp[1][j][k], dp[1][jj][k] + loc[1][j]);if (loc[2][jj] != -1)dp[1][j][k] = min(dp[1][j][k], dp[2][jj][k] + loc[1][j]);}}//中间其余行，只有中间行存在passfor (int i = 2; i < r; i++){if (loc[i][j] == -1) //此路不通continue;pass = is_pass[i][j]; //若这个地方是pass，计算dp是k+1，否则pass是0//左上，左中，左下for (int pos = -1; pos <= 1; pos++){if (loc[i + pos][jj] == -1)continue;for (int k = 0; k < 11; k++){dp[i][j][k + pass] = min(dp[i][j][k + pass], dp[i + pos][jj][k] + loc[i][j]);}}}//最后一行if (loc[r][j] != -1){for (int k = 0; k < 11; k++){if (loc[r - 1][jj] != -1)dp[r][j][k] = min(dp[r][j][k], dp[r - 1][jj][k] + loc[r][j]);if (loc[r][jj] != -1)dp[r][j][k] = min(dp[r][j][k], dp[r][jj][k] + loc[r][j]);}}}for (int i = 1; i <= r; i++){if (loc[i][c]!=-1 && dp[i][c][n] < ans)ans = dp[i][c][n];}if(ans!=inf) printf("%lld",ans);else printf("impossible");return 0;
}