傳送門
簡(jiǎn)單但不是很容易過的一道DP題。
狀態(tài)和轉(zhuǎn)移方程比較容易想。但是注意的地方很多，一不小心就WA了。
思路:首先對(duì)木板按高度從低到高排序，設(shè)置兩個(gè)數(shù)組left[],right[].分別表示從第i塊木板的左(右)端點(diǎn)到地面的最短時(shí)間。如果不能到達(dá)就用-1表示。然后從小到大進(jìn)行遞推，對(duì)于中間的兩塊木板i,j。假設(shè)如果第i塊木板的左端點(diǎn)落在第j塊木板中間，而且兩塊木板中間沒有被隔開，那么第i塊木板的左端點(diǎn)的最小值可以由第j塊木板得到，右端點(diǎn)的分析和左端點(diǎn)相似。當(dāng)然用-1表示不能到達(dá)時(shí)有一點(diǎn)要注意的就是改變left和right的值時(shí)，一定要注意第j塊木板的左端點(diǎn)(或者右端點(diǎn))能否到達(dá)地面也就是說是否是-1.這一點(diǎn)容易被忽視。
附詳細(xì)注釋的代碼