AC. 梦想

frank_c1

[ZJOI 2013] 蚂蚁寻路

发布于2017年03月02日 | 暂无评论 | 330阅读 | 动态规划

题意简述

给定一个n \times m的带权网格。

要求在网格中选出一个封闭图形。具体可以用一条路线描述。

开始位置在某一格点上,方向朝向北。接着右转两次,左转两次,右转两次,左转两次…… 最后再右转一次。规定这条路线上,不能连续旋转两次,不能经过重复的点,最后需要回到起始点,且左转的次数除以2等于k

求所有能选出的图形中,点权和最大的是多少。

1 \le n, m \le 100, 0 \le k \le 10, |A_{i,j}| \le 10 ^ 4

算法讨论

ZJOI居然有这样的题……

我们在纸上画一画,就发现其实这个图形就是2k + 1矩形并在一起,满足矩形同底,且高低严格交替,第一位是高位。

分析出这些性质,基本就解决了。先枚举底的x坐标,设f(i,j,k)为在y坐标为ix坐标为j,现在到第k个矩形的最大权值。按i为阶段转移,对于两个矩形间的转移,暴力转移单次是O(n)的,运用前缀max可以优化到单次O(1)

时间复杂度O(nmk)