斜率优化入门 任务分配

终于开始斜率优化了。。
洛谷P2365 任务安排

题目描述

nn 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 nn 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 ii 个任务单独完成所需的时间为 titi​。在每批任务开始前，机器需要启动时间 ss，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 fifi​。请确定一个分组方案，使得总费用最小。

输入格式

第一行一个正整数 nn。
第二行是一个整数 ss。

下面 nn 行每行有一对数，分别为 titi​ 和 fifi​，表示第 ii 个任务单独完成所需的时间是 titi​ 及其费用系数 fifi​。

输出格式

一个数，最小的总费用。

输入输出样例

5
1
1 3
3 2
4 3
2 3
1 4

153

说明/提示

【数据范围】
对于 100%100% 的数据，1≤n≤50001≤n≤5000，0≤s≤500≤s≤50，1≤ti,fi≤1001≤ti​,fi​≤100。

【样例解释】
如果分组方案是 {1,2},{3},{4,5}{1,2},{3},{4,5}，则完成时间分别为 {5,5,10,14,14}{5,5,10,14,14}，费用 C=15+10+30+42+56C=15+10+30+42+56，总费用就是 153153。

朴素方程很简单，f[i][j]表示把前i个任务分为j组的时候的最小代价
转移显然
这题要求O(n^2),这种转移是O(n^3),不能通过
这边还是把方程写出来了

额，j只和j-1有关，可以优化一维的空间
但是这边没什么必要
考虑优化
有j*SumW[i]这一项，无法单调队列优化
考虑我们要j这一维度的作用，是为了统计S来消除分组带来的后效性
但是仔细考虑，发现这个后效性是可统计的，也就是可以消除
我们每一次分组，增加了S的时间，只需要加上这个S导致的增加的代价即可
所以j这一维可以优化

状态设计变为:
f[i]表示把前i个任务分为了若干组时，算上罚时导致后面的分组代价增加后最小的代价为多少

 转移方程变为

 时间复杂度变为了O(n^2)

这是一个很重要的方法，通过提前统计所有可统计的后效性来优化dp
使用条件还是挺苛刻的，要求一个维度所代表的后效性可统计
多注意一下就好了，算是提供了一种新的优化思路

但是这题时一道斜率优化例题。。
O(n^2)并不是极限
额，方程变个形

 假设k是我们的最优决策点，所以不用管ma
（可以去luogu看这题的题解，讲的很好
我们只需要维护一个决策点的下凸壳，这样里面放的决策点就都是最优决策的候选项
注意开longlong
斜率优化尽量写成相乘的模式，相除容易导致精度的损失而决策错误
因为相乘的原因，所以容易需要开longlong，要注意
正常的情况下，这个队列里面的决策是都需要保留的，但是这题的斜率比较特殊，是SumT[i]+S，显然，随着i的增加，它是单调递增的，所以前面的决策可以直接出队排除
如果不是单调递增的，那么就需要用二分查找来在这个队列里面logn找到需要的决策
还是非常快的

斜率优化。。几乎已经是线性dp的极限了吧？
在求最优解的dp中，结合上线性规划和单调队列的斜率优化，真的是。。
很难理解，也很神奇
使用条件和单调队列有些相似，决策区间单调移动，但是转移方程的形式更加的没有限制，单调队列优化更像是斜率优化的特殊情况

既然i和j的乘积现在也能够考虑了，那，如果是i*i*j或者类似的形式？
i的次方在斜率的部分，这个倒是直接计算就ok，如果是j的次方好像也没什么问题啊
主要是f[j]不太能有次方？假如两边开根号，仿射变换后的坐标系直线会变成斜线，斜率优化就不可能可以用了。。因为线性规划在这样的坐标系里面废掉了
那如果我不开次方，留着呢?
好像可以啊
f[i]在截距里面其实没什么变化，一样转移啊
可以的

这题的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,S,SumT[5001],SumW[5001],f[5001],q[5001];
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read();S=read();
    for(int i=1;i<=n;i++)
    {
        SumT[i]=SumT[i-1]+read();
        SumW[i]=SumW[i-1]+read();
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&(f[q[l+1]]-f[q[l]])<=(S+SumT[i])*(SumW[q[l+1]]-SumW[q[l]]))l++;
        f[i]=f[q[l]]+SumT[i]*(SumW[i]-SumW[q[l]])+S*(SumW[n]-SumW[q[l]]);
        while(l<r&& (f[i]-f[q[r]])*(SumW[q[r]]-SumW[q[r-1]]) <= (f[q[r]]-f[q[r-1]])*(SumW[i]-SumW[q[r]]) )r--;
        q[++r]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}