Difficulty:3- / Easy
Tag:构造
赛时:感觉挺难的样子啊。写了个 O(n3k2)O(n^3k^2)O(n3k2) 的 DP,WA 了不想调了。
睡前:不兑!
我怎么切不了橙了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
先讲构造方法。只需要构造右上 →\rarr→ 左下的数相同即可。如果这种方法构造不出来那就不可能实现。
证明:
首先如果想要 (1,1)→(n,n)(1,1)\rarr (n,n)(1,1)→(n,n) 只有一个值,那 (1,1)→(1,1)\rarr(1,1)→ 每一个格子的值都得确定。这很显然吧,赛时没想出来。
所以每个格不管往上或往左倒推,(1,1)→(1,1)\rarr(1,1)→ 前面那一格的值都得相等。所以一直这么推就能发现如果两个格子到 (1,1)(1,1)(1,1) 曼哈顿距离相等,那它们的值也得相等。
然后分层就能 O(n2)O(n^2)O(n2) 构造了。