題意:
N個任務，每個任務有兩個參數，完成需要的時間t以及因子f，現在將這些任務分組，加工每個分組前機器需要冷卻時間start，完成一組任務耗時為 t + Start + (Tx + Tx+1 + ... + Tx+k)，問最少耗費的時間。
解法：
首先先解決這個問題，在這種分組數不確定的問題中，根據背包九講中無限背包的策略，外層循環只要一層即可完成。
關鍵是內重循環還要枚舉本組的起始位置，如果暴力的做就要N2了。
下面試圖對初始的DP方程進行優化
考慮兩種規劃方向，第一種規劃方向是從前到后
dp[i]=min{dp[k]+(dp[k]+sumt(i)-sumt(k)+start)*(sumf(i)-sumf(k))} 無比復雜的一個式子，推了N小時，在這個式子上下手似乎非常困難。。。（3個決策變量）
但是，如果換種思路，從后向前，將sumt以及sumf重新定義為最后一個任務到第i個任務的時間和和參數和，這樣就簡單多了。
dp[i]=min{dp[k]+(sumt(i)-sumt(k)+start)*sumf(i)}
然后很輕易能發現這個滿足斜率優化的條件（2個待定決策變量，sumt(k)和dp(k)）。
關于斜率優化，一般有代數和幾何兩種方法。先說幾何方法
令g=dp[k]+(sumt(i)-sumt(k)+start)*sumf(i)}，y=dp[k],x=sumt[k]
現在要使g最小
將式子整理下
y=sumf(i)*x+f-(start+sumt(i))*sumf(i)
將這個看做一個線性函數，目標要使得截距最小
再觀察一下，斜率sumf(i)恒為正，且是隨著i單調遞減的，換句話說，是隨著規劃的過程單調遞增的，而自變量x也是隨著規劃的過程單調遞增的。我們畫個圖比劃下
首先，我們要維護的是一個上凹線，因為凹線內部的點不會被斜率為正的直線切到。再者，我們發現最優決策就在凹線的左端。我們來觀察藍色的線，假設這個是第i階段的決策線，灰色凹線與藍色線切點左側的綠色部分顯然是可以丟棄的。應為在切點處截距達到最小。并且在以后的決策中（淺藍色的線），該段同樣不會有任何作用。根據以上觀察，我們可以使用棧隊列（很多人簡稱為單調隊列）的數據結構。這個東西網上介紹的比較多，我就不細說了。
第二種方法就是代數法。
我看網上有一個牛寫的不錯，就貼過來吧- -
初始化的時候要注意，
必須在n+1的位置處加一個虛擬的狀態，不能將第一個狀態（即i=n的狀態）作為初始狀態，因為可能將所有任務僅分為一段。
代碼：
1
# include <stdio.h>
2# define N 10005
3int n,start,st[N],sf[N];
4int q[N],s=-1,e=0;
5int dp[N];
6int cmp(const int a,const int b,const int k)
7
{
8
if(dp[b]-dp[a]<(long long)k*(st[b]-st[a])) return -1;
9 else if((long long)dp[b]-dp[a]==(long long)k*(st[b]-st[a])) return 0;
10 else return 1;
11
}
12int cmp1(const int y1,const int x1,const int y2,const int x2,const int y3,const int x3)
13{
14 if(((long long)y3-y2)*(x2-x1)<((long long)y2-y1)*(x3-x2)) return -1;
15 else if(((long long)y3-y2)*(x2-x1)==((long long)y2-y1)*(x3-x2)) return 0;
16 else return 1;
17}
18int main()
19{
20 int i;
21 scanf("%d%d",&n,&start);
22 for(i=0;i<n;i++)
23 scanf("%d%d",st+i,sf+i);
24 for(i=n-2;i>=0;i--)
25
{
26 st[i]+=st[i+1];
27 sf[i]+=sf[i+1];
28
}
29 q[e]=n;
30 dp[n]=0;
31 for(i=n-1;i>=0;i--)
32 {
33 while(e>=s+2&&cmp(q[s+1],q[s+2],sf[i])!=1) s++;
34 dp[i]=dp[q[s+1]]+(start+st[i]-st[q[s+1]])*sf[i];
35 while(e>=s+2&&cmp1(dp[q[e-1]],st[q[e-1]],dp[q[e]],st[q[e]],dp[i],st[i])!=1) e--;
36 q[++e]=i;
37 }
38 printf("%d\n",dp[0]);
39 return 0;
40}
41