DP_ural_Parliament
因为是图论专题，所以最初想到的是最短路，但是图怎么存？图的最短路需要保存可以经过的点(n*m个点10^6)，肯定爆了，不可能只保存交叉点。果断放弃。
考虑用DP
设当前在(i+1,j+1)表示到达这个点的最短距离。可以到达这里的点有三个。
则(i+1,j+1)=min( (i+1,j)+1，(i,j+1)+1，(i,j)+sqrt(2) ) -> 如果有交叉线。
初始状态是矩阵左边 和下边的边界，即(0,i)=(i,0)=i
思考
假设从行开始遍历，再求出到达该行的每一列的距离，则这里当i+1行求出来后，i就没用了.所以每次只需要维护到达所有列的最短距离就可以了。
完整代码 : https://github.com/Iytz/algorithm/blob/master/graph/dp_1C.cpp
核心部分:
for (int r=1; r<=m; ++r) { double NOupdate = d[0]; d[0] += 1.0; for (int c=1; c<=n; ++c){ double save = d[c]; if(has[r][c]) d[c]=NOupdate+sqrt(2); else d[c]=min(d[c-1],d[c])+1; NOupdate = save; } }
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
