都不能更新好困擾...
如果附檔有錯就算了吧...
DP問題...
受夠了阿...
我這題當初大概想了一整天吧
後來看看其實也就這樣...
只是真的很難去想到就是...
也不然啦...只是實作很多沒注意到的地方出現bug...
我當時的思想:
1.暴力解的話，要得知第i根的狀況，最多必須掃過i-1根的值，然而->嚴重TLE
2.
仔細觀察，其實不必
舉 1 3 4 5 2 為例
當我們判斷到第4根(假設前面都判斷完了，並得到正確答案)，
判斷和前面4的關係就好，
5大於前面的4，所以5的答案等於4的答案+1(多了4)，也就是2(4的答案)+1=3
若判斷到2，2小於等於前面的5，所以答案為0
這樣是不是比暴力解快呢?
然而--->WA!!
我想也是，沒那麼輕鬆嘛...
甚至連範例都會錯就是
3.
以1 10 2 4 3 5 7為例
正解是0 1 0 1 0 3 4，然而用第2種思想卻得到0 1 0 1 0 1 2 ??
恩...仔細觀察相信馬上就會發現原因，
當我們要得到第i根的答案時
我們必須還要判斷擋住i-1根的那個棒棒是否也會擋住第i根，
如果會，那才可以直接第i根的答案=第i-1根的答案+1
如果不會被擋住，我們還要把前面的再吃掉才行
至於擋到第i根的棒棒找法也很好找，答案為0代表前一個擋到，答案為1代表前兩個擋到
拆成步驟的話(直接跳到第4根
1 10 2 4 3 5 7
5>3，吃掉3的答案，並判斷擋住3的那根會不會擋住5
1 10 2 4 3 5 7
5>4，沒被擋住，所以也要吃掉4的答案，也要判斷擋住4的那根
1 10 2 4 3 5 7
5<=10，被擋住了，因此不吃掉10的答案，也不用繼續判斷了
最後5的答案就是3的答案(0)+4的答案(1)+吃掉3和4(2)
也就是0+1+2=3
基本上就這樣，而已，知道實作方法，程式碼寫起來也不長
只是DP真的有夠煩惱