LG 2900 [USACO08MAR]土地征用 Land-Acquisition

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转设$f_i$表示前$i$块土地$$fi=\min{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])$$这样的话怎么想都没有办法优化我们发现,如果一块土地被另一块土地所包含(即长和宽都比另一块土地小),那么只需购买那另一块土地即可,于是我们可以据此筛掉其他的土地,只剩下一些长度递减,宽度递增的土地那么:$$fi=\min{j=1}^{i-1}(f_j+l[j+1]\times w[i])$$设任意$0\le j<k<i$,若从$j$转移比从$k……