題目：http://poj.org/problem?id=3186
一正整數陣列a[]有N(2000)個元素一字排開
從第一輪開始，每輪只能從最左端或最右端拿走一個數字，得分=輪數*a[i]
問最大得分
程式碼：http://codepad.org/YowdOPbo
貪心的反例
4
101 1 102 100 答案是811，貪心會得713
這時候由於利潤函數沒有什麼特別的規則可循
很好地體現了動態規劃的優點
定義DP函數f(p,q)代表盤面a[p]...a[q]的最大得分
有遞回式
f(p,q) = max(f(p+1,q) + a[p]*num , f(p,q-1)+a[q]*num )
num = N-q+p (即第num輪)
挺水的一道DP
沒有留言:
張貼留言