返回信息流Description
A robot is located at the top-left corner of a m×nm×n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. There is a non-negative integer in each small grid which means the score that the robot get when it passes this grid. Now you need to calculate the top kk total scores when the robot reach the destination.
Note: The top k total scores may contain same total score got from different paths.
Input
The first line of input are m and n,which denote the size of the grid. The second line of input is the kk. The next m lines are the score matrix. (1≤m,n,k≤1001≤m,n,k≤100,and 0≤score≤1000≤score≤100)
Output
There is only one line in the Output,which is a descending sequence consist of the top k total scores.
Sample1
Input
3 3
2
3 2 5
3 2 2
4 2 1
Output
13 13
Sample2
Input
4 3
3
7 1 5
4 6 2
4 2 1
5 7 3
Output
30 29 27
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96916同步于 2018/10/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】还是上次那个孩子!!!
ferrarifei
2018/10/21镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
居然第一反应直接转k短路用Astar解决，太暴力了
对于每个状态dp[i][j]维护一个size为k的小根堆
然后dp[i][j]的堆，就直接把dp[i][j - 1]和dp[i - 1][j]两个堆里所有元素都加上v[i][j]扔进来
然后如果size超过了k就不断pop
结果就是dp[n][m]的堆里的元素
空间O(NMK)，时间O(NMK*logK)