廢話在後面講
以下引用自2006冬令營湯澤**：
斜率優化，亦就是說把決策與決策之間表示成乙個類似斜率的式子，進一步分析其中的單調性，並用佇列維護其有用決策。因此斜率優化又稱為佇列優化。
我們來看下**中講的鋸木場選址 （ceoi2004）
[題目描述]
從山頂上到山底下沿著一條直線種植了n棵老樹。當地的**決定把他們砍下來。為了不浪費任何一棵木材，樹被砍倒後要運送到鋸木廠。
木材只能按照乙個方向運輸：朝山下運。山腳下有乙個鋸木廠。
另外兩個鋸木廠將新修建在山路上。你必須決定在**修建兩個鋸木廠，使得傳輸的費用總和最小。假定運輸每公斤木材每公尺需要一分錢。
任務你的任務是寫乙個程式：
從標準輸入讀入樹的個數和他們的重量與位置
計算最小運輸費用
將計算結果輸出到標準輸出
輸入輸入的第一行為乙個正整數n——樹的個數（2≤n≤20 000）。樹從山頂到山腳按照1，2……n標號。
接下來n行，每行有兩個正整數（用空格分開）。
第i+1行含有：wi——第i棵樹的重量（公斤為單位）和di——第i棵樹和第i+1棵樹之間的距離，1≤wi≤10 000，0≤di≤10 000。最後乙個數dn，表示第n棵樹到山腳的鋸木廠的距離。
保證所有樹運到山腳的鋸木廠所需要的費用小於2000 000 000分。
輸出輸出只有一行乙個數：最小的運輸費用。
樣例輸入
91 2
2 13 3
1 13 2
1 62 1
1 21 1
樣例輸出
26[演算法分析]
初步分析：我們明確題目的核心：最優值問題。再加上樹木只能往下傳送，滿足無後效性。那麼此題用動態規劃解決是十分明顯。
進一步分析：題目中說明第n棵樹下面還有乙個鋸木廠，不妨把它當作第n+1個位置來考慮。為了分析的方便，我們增設幾組變數：
sw[i]表示1~i棵樹的總重量，表示式為，時間複雜度為o(n)。
sd[i]表示1~i棵樹的距離，表示式為，時間複雜度為o(n)。
cost[i]表示把第一鋸木場設在第i棵樹的位置上，1~i棵樹到i所需的費用。表示式為，時間複雜度為o(n)。
all[i,j]表示把第i~j棵木頭都運送到第j棵樹的位置上所需要的費用。表示式為，對於求每一項所需的時間複雜度為o(1)。
接下來，設狀態列方程。
設f[i]表示第二個鋸木廠設在i處所需的總費用。
那麼狀態轉移方程為：
該方程的時間複雜度為o(n2)，這遠遠不能滿足題目的要求n<=20000。因此我們必須對其進行優化。
優化：提出這樣乙個設想：假設當前第二鋸木廠設定在i，而它的最優決策為k，也就是說求出的f[i] 值是當j取k時得到的，而對於f[i+1]的最優決策k1必然大於等於k。
下面我們對其進行證明。
由此可知slope[1~k-1,k]<=sd[i](因為k為f[i]的最優決策),而對於f[i+1]有sd[i+1]>=sd[i]，即知slope[1~k-1,k]<=sd[i+1],所以f[i+1]的最優決策k1>=k;
繼續看**：
由此我們可以得知，決策j是滿足單調性的。
如何來維護這種單調性呢？
不難發現slope[j1,j2](j1維護決策的過程中既要維護決策的有序性，而且還要支援在前端的刪除和後端的新增。理所當然我們選擇用佇列來維護。
佇列中需要滿足的以下兩個性質：
佇列所需要滿足的就是乙個上凸的性質。
根據以上的兩個性質，我們對佇列的維護進行如下的2個操作：
設該隊列為list，其中h為隊頭座標，t為隊尾座標。
1、在計算f[i]之前，從隊頭開始掃瞄，若當前slope[list[h],list[h+1]]<=sd[i]，也就是說list[h+1]比list[h]更優則刪除list[h]元素。
2、在計算f[i]之後，將i新增到隊尾，並維護好佇列的性質2。
我們所面臨的情況無非是兩種：
(1)slope[list[t-1],list[t]] (2)slope[list[t-1],list[t]]>=slope[list[t],i],如下圖：
此時，如果有sd[i]>=slope[list[t-1],list[t]]>=slope[list[t],i],即list[t-1]不比list[t]優，同時有list[t]不比i優，所以有了i決策後，就沒必要有list[t]了，於是刪list[t];
時間複雜度：對於每一次求f[i]，只需要o(1)的時間取隊首元素即可。總時間複雜度為o(n)。
以上斜體字是我看**所沒看懂自己加的（我很笨）；
第一次是學斜率的時候沒懂，xlmj神牛講的；
結果第二次再看斜率，又不懂了，lf神牛給我證了一次
於是決定記下來
關於斜率的題：
原來寫了乙個星期，沒總結，看到再加上來
工業用的DP網
資料處理 data processing dp 是對資料的採集 儲存 檢索 加工 變換和傳輸。資料是對事實 概念或指令的一種表達形式，可由人工或自動化裝置進行處理。資料的形式可以是數字 文字 圖形或聲音等。資料經過解釋並賦予一定的意義之後，便成為資訊。資料處理的基本目的是從大量的 可能是雜亂無章的 ...
2 1 1直線的斜率 1
2.1.1 直線的斜率 1 教學目標 1 理解直線的斜率的概念，掌握過兩點的直線的斜率公式 2 使學生初步感受直線的方向與直線的斜率之間的對應關係，從而體會到要研究直線的方向的變化規律，只要研究直線斜率的變化規律 教學重點 過兩點的直線的斜率公式的運用 教學方法 合作交流法 教學過程 一 問題情境 ...
動態規劃DP的使用條件
任何思想方法都有一定的侷限性，超出了特定條件，它就失去了作用。同樣，動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最優化原理和無後效性。1.最優化原理 最優子結構性質 最優化原理可這樣闡述 乙個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最...