动态规划——提高Ⅴ（DP优化）

其他例题（摘自AcWing）

在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。

现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。

然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。

FJ 有 N 只排成一排的奶牛，编号为 1 到 N。

每只奶牛的效率是不同的，奶牛 i 的效率为 Ei。

编号相邻的奶牛们很熟悉，如果 FJ 安排超过 K 只编号连续的奶牛，那么这些奶牛就会罢工去开派对。

因此，现在 FJ 需要你的帮助，找到最合理的安排方案并计算 FJ 可以得到的最大效率。

注意，方案需满足不能包含超过 K 只编号连续的奶牛。

输入格式
第一行：空格隔开的两个整数 N 和 K；

第二到 N+1 行：第 i+1 行有一个整数 Ei。

输出格式
共一行，包含一个数值，表示 FJ 可以得到的最大的效率值。

数据范围
1≤N≤105,
0≤Ei≤109
输入样例：
5 2
1
2
3
4
5
输出样例：
12
样例解释
FJ 有 5 只奶牛，效率分别为 1、2、3、4、5。

FJ 希望选取的奶牛效率总和最大，但是他不能选取超过 2 只连续的奶牛。

因此可以选择第三只以外的其他奶牛，总的效率为 1 + 2 + 4 + 5 = 12。

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
LL s[N];
LL f[N];
int q[N];

LL g(int i)
{
    if (!i) return 0;
    return f[i - 1] - s[i];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (q[hh] < i - m) hh ++ ;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while (hh <= tt && g(q[tt]) <= g(i)) tt -- ;
        q[ ++ tt] = i;
    }

    printf("%lld\n", f[n]);

    return 0;
}


                                           

John 打算驾驶一辆汽车周游一个环形公路。

公路上总共有 n 个车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。

John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。

在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

输入格式
第一行是一个整数 n，表示环形公路上的车站数；

接下来 n 行，每行两个整数 pi,di，分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。

输出格式
输出共 n 行，如果从第 i 号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第 i 行输出 TAK，否则输出 NIE。

数据范围
3≤n≤106,
0≤pi≤2×109,
0≤di≤2×109
输入样例：
5
3 1
1 2
5 2
0 1
5 4
输出样例：
TAK
NIE
TAK
NIE
TAK

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 2e6 + 10;

int n;
int oil[N], dist[N];
LL s[N];
int q[N];
bool ans[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &oil[i], &dist[i]);
        s[i] = s[i + n] = oil[i] - dist[i];
    }
    for (int i = 1; i <= n * 2; i ++ ) s[i] += s[i - 1];

    int hh = 0, tt = 0;
    q[0] = n * 2 + 1;
    for (int i = n * 2; i >= 0; i -- )
    {
        if (q[hh] > i + n) hh ++ ;
        if (i < n)
        {
            if (s[i] <= s[q[hh]]) ans[i + 1] = true;
        }
        while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;
        q[ ++ tt] = i;
    }

    dist[0] = dist[n];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = oil[i] - dist[i - 1];
    for (int i = 1; i <= n * 2; i ++ ) s[i] += s[i - 1];

    hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i <= n * 2; i ++ )
    {
        if (q[hh] < i - n) hh ++ ;
        if (i > n)
        {
            if (s[i] >= s[q[hh]]) ans[i - n] = true;
        }
        while (hh <= tt && s[q[tt]] <= s[i]) tt -- ;
        q[ ++ tt] = i;
    }

    for (int i = 1; i <= n; i ++ )
        if (ans[i]) puts("TAK");
        else puts("NIE");

    return 0;
}


                          

高二数学《绿色通道》总共有 n 道题目要抄，编号 1,2,…,n，抄第 i 题要花 ai 分钟。

小 Y 决定只用不超过 t 分钟抄这个，因此必然有空着的题。

每道题要么不写，要么抄完，不能写一半。

下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。

这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。

现在，小 Y 想知道他在这 t 分钟内写哪些题，才能够尽量减轻马老师的怒火。

由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

输入格式
第一行为两个整数 n,t。

第二行为 n 个整数，依次为 a1,a2,…,an。

输出格式
输出一个整数，表示最长的空题段至少有多长。

数据范围
0
#include 
#include 

using namespace std;

const int N = 50010, INF = 1e9;

int n, m;
int w[N];
int f[N], q[N];

bool check(int k)
{
    f[0] = 0;
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (hh <= tt && q[hh] < i - k - 1) hh ++ ;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = INF;
    for (int i = n - k; i <= n; i ++ ) res = min(res, f[i]);

    return res <= m;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}

有一个 a×b 的整数组成的矩阵，现请你从中找出一个 n×n 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入格式
第一行为三个整数，分别表示 a,b,n 的值；

第二行至第 a+1 行每行为 b 个非负整数，表示矩阵中相应位置上的数。

输出格式
输出仅一个整数，为 a×b 矩阵中所有“n×n 正方形区域中的最大整数和最小整数的差值”的最小值。

数据范围
2≤a,b≤1000,
n≤a,n≤b,n≤100,
矩阵中的所有数都不超过 109。

输入样例：
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例：
1

#include 
#include 
#include 

using namespace std;

const int N = 1010, INF = 1e9;

int n, m, k;
int w[N][N];
int row_min[N][N], row_max[N][N];
int q[N];

void get_min(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}



int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]);

    for (int i = 1; i <= n; i ++ )
    {
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }

    int res = INF;
    int a[N], b[N], c[N];
    for (int i = k; i <= m; i ++ )
    {
        for (int j = 1; j <= n; j ++ ) a[j] = row_min[j][i];
        get_min(a, b, n);

        for (int j = 1; j <= n; j ++ ) a[j] = row_max[j][i];
        get_max(a, c, n);

        for (int j = k; j <= n; j ++ ) res = min(res, c[j] - b[j]);
    }

    printf("%d\n", res);

    return 0;
}


  

斜率优化DP

所谓1D/1D动态规划，指的是状态数为O(n)，每一个状态决策量为O(n)的动态规划方程，直接求解的时间复杂度是O(n2)。但是，绝大多数的方程通过合理的组织与优化都是可以直接优化到O(nlogn)乃至O(n)的时间复杂度的。
优化方法包括：

• 单调队列优化至O(n)

• 斜率优化至O(nlogn)或O(n)

• 决策单调性优化至O(nlogn)

斜率优化算法简介

斜率优化Dp问题入门会较为困难，因为这大概是在学习过程中OI选手第一次遇到与数学内容结合的算法。
但斜率优化反而是一个重要的知识点，它简单地将1D/1D动态规划优化至O(n)，同时斜率优化也有更困难的延申与拓展。
其中最简单的斜率优化形式还是单调队列，但优化原理大不相同。

对于一个决策j进行考虑，即将考虑的转移是：
f(i)=a[i]×x(j)+b[i]×y(j)。
我们使用线性规划进行转化（线性规划大概会在高二学习），
我们以x(j)为横轴，y(j)为纵轴建立平面直角坐标系，这样决
策j就可以用坐标系上的一个点表示。
原方程可以转化为f(i)=min{a[i]×x+b[i]×y}，这类似一个
直线的一般式方程，我们将其转化为斜截式方程：y=?abx+f(i)b，假设b>0，则目标是最小化直线的纵截距。
我们用一个斜率为?ab的直线从负无穷向上平移，所碰到的第
一个点即为最优决策j，利用这个点我们可以计算出最优的
f(i)。

不难发现，所有可能的最优决策点必定在平面点集的凸包上，换句话说不在凸包上的点一定不是最优决策点。
当b>0时，我们需要维护一个右下凸包或左上凸包（根据点集的特征决定）。
那么现在我们的任务转化为了维护凸包。
根据直线斜率和数据点分布的特征，我们可以分为三种情况。

1.决策直线的斜率与二元组的横坐标同时满足单调性

这种情况的处理非常简单，因为斜率变化是单调的，因此决策点必然在凸壳上单调移动，我们只需要维护一个单调队列和一个决策指针即可。
对于每一个状态f(i)，计算过程如下：

• 决策指针（队首）后移，直到最佳决策点j。

• 进行决策并计算f(i)。

• 计算x(i),y(i)，将二元组加入队尾，同时更新凸壳（如图）。

时间复杂度O（n）

2.二元组的横坐标满足单调性

我们使用同样的方式维护凸壳，在查询最优决策点的时候，使用二分查找找到最接近的斜率。

时间复杂度为O(nlogn)

3.不满足任何限制

虽然决策点仍然在凸壳上，但是在维护凸壳时就有大麻烦了。我们需要一一验证凸性，接着需要拼接凸壳，最坏的时间复杂度O(n)，这相当于根本没有优化！
该怎么做呢？分为两种情况：

• 允许离线：此时我们可以使用cdq分治（上我的博客里的提高算法目录中自己翻）来较为简单地解决这个问题，时间复杂度为O(nlogn)。

• 强制在线：此时我们只能使用平衡树来维护凸包了，我们以横坐标为关键字建立平衡树，查找和插入的过程均为O(nlogn)，在维护凸壳时，先将新数据点Splay到根结点，剩下的结点必定分居左子树与右子树。然后我们以左子树为例，后序遍历依次查找结点，直到找到一个满足凸性的结点，将这个结点Splay到根结点的左儿子，然后我们删掉这个结点的右子树即可，时间复杂度为O(nlogn)，但实现起来非常复杂。

例题

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入格式
第一行包含整数 N。

第二行包含整数 S。

接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

输出格式
输出一个整数，表示最小总费用。

数据范围
1≤N≤5000,
0≤S≤50,
1≤Ti,Ci≤100
输入样例：
5
1
1 3
3 2
4 3
2 3
1 4
输出样例：
153

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 5010;

int n, s;
int sc[N], st[N];
LL f[N];

int main()
{
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &st[i], &sc[i]);
        st[i] += st[i - 1];
        sc[i] += sc[i - 1];
    }

    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < i; j ++ )
            f[i] = min(f[i], f[j] + (sc[i] - sc[j]) * (LL)st[i] + (LL)s * (sc[n] - sc[j]));

    printf("%lld\n", f[n]);

    return 0;
}


有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入格式
第一行包含整数 N。

第二行包含整数 S。

接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

输出格式
输出一个整数，表示最小总费用。

数据范围
1≤N≤3×105,
1≤Ti,Ci≤512,
0≤S≤512
输入样例：
5
1
1 3
3 2
4 3
2 3
1 4
输出样例：
153
                              
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 300010;

int n, s;
LL c[N], t[N];
LL f[N];
int q[N];

int main()
{
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &t[i], &c[i]);
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }

    int hh = 0, tt = 0;
    q[0] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh ++ ;
        int j = q[hh];
        f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
        while (hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;
        q[ ++ tt] = i;
    }

    printf("%lld\n", f[n]);

    return 0;
}

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入格式
第一行包含两个整数 N 和 S。

接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

输出格式
输出一个整数，表示最小总费用。

数据范围
1≤N≤3×105,
0≤S,Ci≤512,
?512≤Ti≤512
输入样例：
5 1
1 3
3 2
4 3
2 3
1 4
输出样例：
153
  
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 300010;

int n, s;
LL t[N], c[N];
LL f[N];
int q[N];

int main()
{
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &t[i], &c[i]);
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }

    int hh = 0, tt = 0;
    q[0] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        int l = hh, r = tt;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) r = mid;
            else l = mid + 1;
        }

        int j = q[r];
        f[i] = f[j] -   (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
        while (hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (double)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;
        q[ ++ tt] = i;
    }

    printf("%lld\n", f[n]);

    return 0;
}

小 S 是农场主，他养了 M 只猫，雇了 P 位饲养员。

农场中有一条笔直的路，路边有 N 座山，从 1 到 N 编号。

第 i 座山与第 i?1 座山之间的距离为 Di。

饲养员都住在 1 号山。

有一天，猫出去玩。

第 i 只猫去 Hi 号山玩，玩到时刻 Ti 停止，然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 1 号山走到 N 号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为 1 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 1 的山，一只猫在 2 号山玩，玩到时刻 3 开始等待。

如果饲养员从 1 号山在时刻 2 或 3 出发，那么他可以接到猫，猫的等待时间为 0 或 1。

而如果他于时刻 1 出发，那么他将于时刻 2 经过 2 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 1 号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式
第一行包含三个整数 N，M，P。

第二行包含 n?1 个整数，D2,D3,…,DN。

接下来 M 行，每行包含两个整数 Hi 和 Ti。

输出格式
输出一个整数，表示所有猫等待时间的总和的最小值。

数据范围
2≤N≤105,
1≤M≤105,
1≤P≤100,
1≤Di<1000,
1≤Hi≤N,
0≤Ti≤109
输入样例：
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
输出样例：
3
           
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 100010, M = 100010, P = 110;

int n, m, p;
LL d[N], t[N], a[N], s[N];
LL f[P][M];
int q[M];

LL get_y(int k, int j)
{
    return f[j - 1][k] + s[k];
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);

    for (int i = 2; i <= n; i ++ )
    {
        scanf("%lld", &d[i]);
        d[i] += d[i - 1];
    }

    for (int i = 1; i <= m; i ++ )
    {
        int h;
        scanf("%d%lld", &h, &t[i]);
        a[i] = t[i] - d[h];
    }

    sort(a + 1, a + m + 1);

    for (int i = 1; i <= m; i ++ ) s[i] = s[i - 1] + a[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= p; i ++ ) f[i][0] = 0;

    for (int j = 1; j <= p; j ++ )
    {
        int hh = 0, tt = 0;
        q[0] = 0;

        for (int i = 1; i <= m; i ++ )
        {
            while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh])) hh ++ ;
            int k = q[hh];
            f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i];
            while (hh < tt && (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt]) >=
                (get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt - 1])) tt -- ;
            q[ ++ tt] = i;
        }
    }

    printf("%lld\n", f[p][m]);

    return 0;
}

决策性单调优化DP

决策单调性算法简介

决策单调性可以理解为四边形不等式优化Dp的1D/1D版本。
可以利用决策单调性优化的动态规划的特点是：其决策的下标单调。

特征方程：\(f(x)=\)\(\min_{i=1}^{x-1}\){\(f(i)+w[i,x]}\)

已知结论

如果用k(x)表示状态x取到最优值的决策，则决策单调性表述为：

\(?i≤j,k(i)≤k(j)\)当且仅当：

\(?i≤j\),w[i,j]+w[i?1,j?1]≤w[i?1,j]+w[i,j?1]

因此满足转移代价四边形不等式，则可以利用决策单调性进行优化。

但是转移的代价是否满足四边形不等式，并非一个很容易判断的问题，因此推荐的姿势是：

在确认动态规划需要优化且不满足以上两种方式时，打表验证决策点是否单调。

记G(x,i)为状态x根据转移方程f(x)使用i决策转移的结果。

设决策点i，决策j比i更优（假设问题要求最小化），则G(x,i)≥G(x,j)