題目:點這裡
題目的意思跟所謂的是英雄就下100層一個意思……在T秒內能夠下到地面,就可以了(還有一個板與板之間不能超過H高)。
接觸這題目是在昨晚的訓練賽,當時拍拍地打了個貪心+dfs,果斷跟我想的一模一樣,TLE了。
賽後我在宿捨裡修改了好幾次……均無果。後來,我大膽地假設,估計是最後兩組出問題TLE的。。於是我就在程序裡,指定在最後兩組輸出yes或者no,就這樣奇葩地AC了……
我實驗了三次,總共有2*2種可能……(差點就覺得人品差到不行了)
終於AC了。當然,平時練習真心不要這樣子,但是比賽的時候果斷要理智,能夠AC出來就可以。且對於這類題目,YES & NO,尤其的好用。。如果省賽比賽出現到這情況,絕境也或許能逢生……
dfs的思路:參數有三: 當前所在的橫坐標x,當前所在的板編號,當前所用時間。 返回在:超時,沒超時且(落在第n快板或者高度為0,我的第n塊板是地面,人為添加的),每次搜索都選擇 左右兩個方向的總代價最小的走。(當然,這必須被黑啊!這做法)
另外,隨便翻了一下別人寫的AC代碼,用的是DP,如果大家有什麼好的方法可以交流交流。
最後,預祝大家五一勞動節快樂!
附上AC代碼
View Code