首页 > Working out
开通博客写题解
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-08 15:52:11
Working Out 题目大意: 给定一个矩阵，每个点都有一个点权，让你求从矩阵中某一点到矩阵四个顶点的权值之和减去自己的四倍的值最大(就是这个点没有贡献) 分析： 我们画两张图，看看他们的路径，就会发现其实只有两种情况一:二：就是说其实只有两种转移的方式那么我们用4个数组分别记录到四个顶点的最大 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Dear㉿You
发表于 2020-09-09 15:16:03
翻译(口胡) 有一个n*m大小的健身房，每走到一个点(i,j)，都会消耗a[i][j]大小的卡路里，小西从(1,1)出发走到(n,m)，只 能向右走或向下走，小瓜从(n,1)出发走到(1,m),只能向右走或向上走,他们两人决定在某一个点会面且只进行一次 会面，那个点的卡路里不计入总卡路里。求出小西 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 __故人__
发表于 2020-09-08 18:17:01
分析 一个节点到左上，右上，左下，右下的最大值路径是确定的。那么我们考虑见面的点是哪个点。因为见面点是不能计算贡献的，所以我们考虑第一个人和第二个人是分别从哪个方向来的。经过讨论也只有两种可能。枚举每一个点算出值就可以了。时间复杂度为 。 代码 #include<bits/stdc++.h& 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-08 21:19:44
吐槽 本人感觉题目十分有坑。。。就是因为没有理解真正的题意。。。 两人只能相遇一次 从下边上来的人只能从上边出这个点，从左边进来的人只能从右边出这个点 分析 因为我们需要两个人走对角线，并且复杂度允许所以我们可以直接从4个顶点暴力DPDP[1/2/3/4][i][j]表示从某个顶点到的最大权值和 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 程序蒟蒻
发表于 2020-09-11 22:41:31
其实这个倒着想就行，从一个点出发到四个角的距离最大，正好还不用处理自己本身的值，如果正常思维的话会很麻烦并且不会写。。。一共两种情况，ans两种判断方式。设四个数组分别表示到四个角的最大距离 #include<iostream> #include<string> #inclu 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 熠丶
发表于 2020-09-08 18:57:08
思路： 先设dp1,dp2,dp3,dp4[i][j]分别是从矩阵的四个顶点（以左上为起点顺时针，记为A,B,C,D）走到(i,j)的点数之和 枚举两人可能相遇的点，求ans的最大值 相遇点走法有两种可能性： 1：A->C可能是经过该点上方后走到该点下方，B->D是左到右 2：A-&g 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Acapplella
发表于 2020-09-13 11:22:03
思路:我们可以直接从4个顶点暴力DP。DP[1/2/3/4][i][j]表示从某个顶点到(i,j)的最大权值和。求出之后，我们可以直接枚举相遇点计算到达最终点的权值和最大即可。参考代码如下: #include <cstdio> #include <algorithm> us 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”