考虑这道题大多数题解用的是搜索,这样的复杂度按理来说是 O(nV2V) 的。(V 是字符串长度)
但是在极限数据:
10
*******************
******************
*****************
****************
***************
**************
*************
************
***********
**********
下,没有一个题解是跑过了的,而最优解和搜索在倒数第二个情况(就是有 11 个 *)的时候输出不同。
是搜索的复杂度假了,还是常数太大,或者是题面描述有误?
本来想加 hack 数据的,但是考虑到加了之后可能没有不超时的可行解,所以想询问洛谷上的大佬们。/kel