写在前面：

在做斜率优化的题目的时候，一定要记得，在编译之前看一遍整个代码，看看公式推得正确不正确，验证一下函数返回的值是否正确，然后顺一遍思路。不然你会Debug很惨很惨……

总结一下在写斜率优化的时候犯下的错误：

  1. head++写成了head–
  2. 在进行计算斜率的时候应该是写Queue[head]/Queue[tail]结果写成了head/tail
  3. tail–写成了tail++
  4. 更新队尾的时候应该让tail和tail-1比而不是tail和tail+1比
  5. 用前缀和后缀和进行运算的时候要-而不是+（可恶啊！！！）

斜率优化在我看来是比较玄学的一种优化，和单调性优化相似，都是需要将方程进行变形，变形之后寻找一种斜率关系，然后通过斜率的大小来比较最优值（有可能方程变形的时候是由正着的然后优化的时候必须变成倒着推才能将方程变形成一种斜率关系，大概是找方程中元素越少越好QAQ

  • 其实需要将方程变形成一种关系,也就是只有以下是含有变量j的
  • 因为比较抽象，所以说还是结合着题目进行学习吧

优化决策

然后大力总结一发，我们首先将状态转移方程化为能写成与变量有关和与变量无关的两部分，然后对于决策x比y优秀(取值是x>y还是x<y取决于推导过程是从后往前还是从前往后)，得出一个条件式，然后将条件式化为斜率式，最后根据斜率式用队列保留最优值。

这一类题真的是超级麻烦，需要徒手推公式的QAQ

下面的题目具体的过程不再给出，就是一个方程加上斜率式加上代码了……

P1328任务安排

题目描述：

  • N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。
  • 例如：S=1；T={1,3,4,2,1}；F={3,2,3,3,4}。如果分组方案是{1,2}、{3}、{4,5}，则完成时间分别为{5,5,10,14,14}，费用C={15,10,30,42,56}，总费用就是153。

输入：

  1. 第一行是N(1<=N<=50000)。
  2. 第二行是S(0<=S<=50).
  3. 下面N行每行有一对数，分别为Ti和Fi，均为不大于100的正整数，表示第i个任务单独完成所需的时间是Ti及其费用系数Fi。

输出：

一个数，最小的总费用.

题解：

这道题其实我们是可以很顺利的列出状态转移方程的，预处理出来前缀和F和T，然后顺

1
f[i]=min(f[i],f[j]+T[i]*(F[i]-F[j])+S*(F[n]-F[j]));

很显然，这样是没有办法AC这道题的，对于50000的数据，二重循环是要超时的。我们只能再次进行优化，但是这个方程对于我们来说变形是有些困难的，能不能再简单一些呢，比如后面的S*(F[n]-F[j])如果倒着推不久可以省略掉了吗.

我们再次处理F和T两个数组，进行逆向前缀和：

1
2
3
4
5
for(int i=n-1;i>=1;i--)
   {
       T[i]+=T[i+1];
       F[i]+=F[i+1];
   }

这样我们就可以将方程化简为（推导是从后往前）：

1
f[i]=min(f[i],f[j]+(T[i]-T[j]+s)*F[i]);

我们和在用单调性来优化DP的时候一样，将所有和j有关的变量放在一起，然后状态转移方程就变成了这样：

1
f[i]=min(f[i],(f[j]-T[j]*F[i])+(T[i]+S)*F[i]);

也就是说，如果决策x优于决策y的时候，存在加黑的地方f(x)>f(y)并且需要满足x<y的。那么我们就可以得到当x优于y的时候的条件：

1
f[x]-T[x]*F[i]<f[y]-T[y]*F[i];

然后提出和决策无关的东西；

1
f[x]-f[y]<(T[x]-T[y])*F[i];

然后变形为斜率式；

1
(f[x]-f[y])/(T[x]-T[y])<F[i];

好的斜率式出来了QAQ……

我们建立一个队列，然后每次在开始的时候比较队头和队头的下一个元素，如果队头的下一个元素是满足 (f[x]-f[y])/(T[x]-T[y])<F[i] ;这个式子那么就可以说明队头+1的决策是优于队头的，那么我们就可以将队头进行更新掉了。

我们之所以可以对队头进行更新，原因就是一旦满足 (f[x]-f[y])/(T[x]-T[y])<F[i] ;这个式子，由于 F[i] 是单调递增的，所以说在以后 (f[x]-f[y])/(T[x]-T[y]) 是绝对大于 F[i] 的。那么如果队头+1优于队头，那么队头+1永远优于队头。因而我们可以进行更新。

那么如果计算出来一个 f[i] 的时候如何将其塞进队列里面呢，我们需要用到一个式子，如果a和b的斜率小于b和c的斜率，那么b就可以更新掉了，因为我们需要维护一个斜率为单调递增的队列（单调递增才能保证队头元素是最优的），具体证明过程很简单，不再给出（其实是很复杂，不想写QAQ）。

每次在开头淘汰队头，计算出来当前最优值来淘汰队尾，这样不断地从后往前进行更新就好。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iomanip>
using namespace std;
struct Pair
{
    int Time;
    int Cost;
}a[5011];
int n,s,f[5010],Queue[5010],head=1,tail=1;
double Slope(int i,int j)
{ return(1.0*(f[i]-f[j]))/(1.0*(a[i].Time-a[j].Time)); }
int main()
{
    memset(f,0,sizeof(f));
    memset(Queue,0,sizeof(Queue));
    ios::sync_with_stdio(false);
    cin>>n>>s;
    a[0].Cost=0;
    a[0].Time=0;
    f[0]=0;
    for(int i=1;i<=n;i++)
    cin>>a[i].Time>>a[i].Cost;
    for(int i=n-1;i>=1;i--)
    {
        a[i].Time+=a[i+1].Time;
        a[i].Cost+=a[i+1].Cost;
    }
    for(int i=n;i>=1;i--)
    {
        while(head<tail&&Slope(Queue[head+1],Queue[head])<a[i].Cost) head++;
        f[i]=f[Queue[head]]+(a[i].Time-a[Queue[head]].Time+s)*a[i].Cost;
        while(head<tail&&Slope(i,Queue[tail])<Slope(Queue[tail],Queue[tail-1])) tail--;
        Queue[++tail]=i;
    }
    cout<<f[1]<<endl;
    return 0;
}

P1330土地购买

题目描述：

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000).

每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25.

FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

输入：

第1行: 一个数: N 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽；

输出：

第一行: 最小的可行费用.

题解：

这道题恶心的强制全部地方long long ， cin 必须弃疗，排序算法写挂了导致检查不出来，while循环竟然head–（Runtime Error）！预处理各种异想天开，我的代码能力还是太弱了太弱了……

这道题需要预处理一下，将可以顺便带走的土地直接带走（长和宽都小于某一个土地我们就可以忽略它），然后排个序，将x长度上升，y长度下降（不要问我为什么，我也不知道……），然后就当成最普通的DP列出来状态转移方程。

然后一个斜率优化就过了……

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct Edge
{
    long long x;
    long long y;
}a[60000],b[60000];
long long n,f[60000],Max_x=0,Max_y=0;
long long ans=0,Queue[60000],tail=0,head=0;
bool mycmp(Edge a,Edge b)
{ return a.x==b.x?a.y<b.y:a.x<b.x;}
double Slope(long long x,long long y)
{ return (double)(f[x]-f[y])/(b[y+1].y-b[x+1].y); }
int main()
{
    ios::sync_with_stdio(false);
    memset(f,0,sizeof(f));
    memset(Queue,0,sizeof(Queue));
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,mycmp);
    for(int i=1;i<=n;i++)
    {
        while(ans&&a[i].y>=b[ans].y) ans--;
        b[++ans].x=a[i].x;
        b[ans].y=a[i].y;
    }
    for(int i=1;i<=ans;i++)
    {
        while(head<tail&&Slope(Queue[head+1],Queue[head])<b[i].x) head++;
        f[i]=f[Queue[head]]+b[i].x*b[Queue[head]+1].y;
        while(head<tail&&Slope(i,Queue[tail])<Slope(Queue[tail],Queue[tail-1])) tail--;
        Queue[++tail]=i;
    }
    cout<<f[ans]<<endl;
    return 0;
}