------------
#
------------
------------
------------
by 有一点尴尬 @ 2019-04-03 13:59:41
希望更丰富的展现？[使用Markdown](https://www.luogu.org/wiki/show?name=%E5%B8%AE%E5%8A%A9%EF%BC%9Amarkdown)
by Alex_Cui @ 2019-04-03 15:33:06
初步看下来应该是dfs里面judge这层for T了.
你这里采用的是遍历这一行中所有点然后判断这个点是否与棋盘上的点冲突, 假设有 $n\times n$ 的棋盘, 那么需要判断的次数就是 $n^3$. 首先我们考虑第一层优化, 假设当前在 $m$ 行, 那么摆放旗子的实际上只有 $m-1$ 行, 而之后剩余的行根本没有棋子, 所以我们不用判断, 那么```judge```函数中的第一层循环改成如下:
```cpp
for (i = 0; i < y; ++i)
```
这时候我们就把运算次数从 $n^3$ 缩小到了 $\frac{n^3}{2}$ 了, 每一次运算的次数为 $n\times m$.
但是我们考虑到, 每次判断所有**点是否影响这个点**的运算等价于所有的**点所影响的所有点是否包含这个点**, 也就是说同一行中进行的 $n$ 次判断都是一模一样的, 那么我们可以反向思考, 把**所有的点是否影响这个点**化作**这一行中哪些点不被之前的点所影响**, 这时候我们只要每一行 $n\times m$遍历一次就可以了, 然后哪些点可以放棋子就继续dfs, 如果没有点可以放了就直接return, 这样我们又减少了 $n$ 次运算.
最后, 同一行中不可能出现两个"后", 所以储存方面把 $n\times n$ 矩阵化成 $n$ 的数组, 每一项储存当前行的"后"的位置即可, 那么后续中 $n\times n$ 和 $n\times m$的遍历就可以化为 $n$ 和 $m$ 了.
至此, 程序肯定不会T了
by Alex_Cui @ 2019-04-03 15:56:32
@[Alex_Cui](/space/show?uid=91676)
虽然还是不过，但是还是谢谢大佬>_<。。。
by 计算机陈楚玲 @ 2019-04-05 08:35:42