LG 2254 [NOI2005]瑰丽华尔兹

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转$f{t,i,j} = MAX(f{t-1,x',y'})+1$复杂度:$O(Tnm)$,只能过 50%看到$k \le 200$那么我们是不是可以直接用?设$f_{k,i,j}$为在区间$k$中在位置$(i,j)$能最多滑行多远$f{k,i,j} = MAX(f{k-1,i,j},f{k-1,i',j'}+dis{(i,j),(i',j'))})$那么复杂度就是$O(kn^3)$,可以用单调队列优化掉其中一个$n$……