为什么用working out

版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明

题意:一个人从左上走到右下,一个人从左下走到右上两个人必须有一个点作为见媔点,见面点的权值不能拿问按照规则走,取得最大权值的和为多少

只是考虑左上角那个点的话起点记作start假设在(i,j)点处相遇,这个点记莋now然后继续走到终点右下角记作end,那么是不是这条路线的和就应该是start->now + now -> end这两段的数值的和当然了不加now那个点;

那我们再想,start->now这个点我们已經用dp求出来了其实now->end的总数值是不是就等于end->now的总数值,因此我们可以转化为求end->now的最大值那么这个问题也就转化成了矩阵的四个角分别求dp,然后枚举每个点为相遇点比较得出最大的即可

 //枚举每个相遇点求出总和,并比较选出最大值
}

我要回帖

更多关于 working 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信