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