codeforces 429 B. Working out (dp)

cf429 b 题目链接
题意:

n*m个格子,每个格子有一个人value a[i][j]>0,连个人,一个从左上角到右下角,每次只能向下或者向右移动,一个从左下到右上,每次只能向上或者向右移动,现在要求两个人恰好相遇一次,相遇点的a不算数,问在满足这样的条件下使得两个人的a最大。。。(很坑的一点是。。这里相遇并不考虑时间。。就是说,不在同一时间都到达过某一格子,也认为相遇。所以我认为,题目含义更准确的说法是,路径只有一个交点)

思路:很巧妙。先预处理4个二维数组,分别表示点(i,j)到四个角落的最大值。(这个处理很容易,类似数字三角形)

然后枚举相遇的点,对于确定的相遇的点(x,y),我们可以认为是四个角落各连一条线到点(i,j)

由于只能相遇一次,所以连接方式只有两种情况。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz