【bzoj3671】[Noi2014]随机数生成器

2015.07.10 09:22 Fri | 17次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定一个n*m的棋盘,随机填入1-n*m,求从(1,1)到(n,m)的路径中(只能向右或向下),将走过的点排序后字典序最小的路径,排序后输出。n,m<=5000

题解

为什么NOI2014这么水,每天的前两个题都会做……当然考场上一定不会都答上就是了……
这道题就是从1到n*m枚举,如果一个数能选,那么一定要选,选完之后把这个点的左下,右上的点都删除就行了。复杂度也是O(n*m)的,因为每个点只会被删除1次。
这题之前还有一些废话,并且有点卡时……

  • quanquan_wang 2016-03-22 13:52:27

    你确定你的题没有发窜?。。。。。
    @jkxing