题解中提到:
设走到
(n,i) 的方案数为
wi。我们要求的是
i∑i×wi。
这里应该是作者笔误了,反悔贪心里的贡献是减少的1,不是剩下的1。所以应该是"向右上走的次数减去i"。
也就是说下文的式子里:
i≥0∑wi×i=i≥0∑ii+2j≥n∑xj(m−x)n−j((i+jn)−(i+j+1n))
=i≥0∑xi(m−x)n−ij≥max{i,n−i}∑(j−i)((jn)−(j+1n))
应该改为:
i≥0∑wi×(j−i)=i≥0∑i+2j≥n∑(j−i)xj(m−x)n−j((i+jn)−(i+j+1n))
=i≥0∑xi(m−x)n−ij≥max{i,n−i}∑(2i−j)((jn)−(j+1n))