写在前面

  • 其实是动态规划深入讨论的一部分，但是由于内容比较多，所以拆开了。虽然动态规划的复杂度相对于搜索算法来说，已经很优秀了，是搜索算法的一种很强大的优化，但是DP在原来的基础上还是可以继续进行优化的，这其中一种方法就是利用单调性进行优化，适用范围还是挺广的。
  • 单调性的优化其实就是利用你所列出来的状态转移方程中，进行变形，留下来真正的变量，剩下的已经确定的东西我们就可以不用去管了，只需要在真正的变量里面用低上一个维度或者低上更多的时间来得到这个变量的最优值，这种优化就是一种利用数学方面的DP优化。
  • 其次就是DP类型的离散化类型的优化，我们只利用自己需要的值，对于一个维度特别大，达到远大于其他因素的时候，一般都是可以进行离散化优化的……学校的OJ里面大概有两三道题是比较好的，拉出来吧……

DP单调性优化

P1326超级教主

题目描述：

LHX教主很能跳，因为Orz他的人太多了。教主跳需要消耗能量，每跳1米就会消耗1点能量，如果教主有很多能量就能跳很高。教主为了收集能量，来到了一个神秘的地方，这个地方凡人是进不来的。在这里，教主的正上方每100米处就有一个能量球（也就是这些能量球位于海拔100，200，300……米处），每个能量球所能提供的能量是不同的，一共有N个能量球（也就是最后一个能量球在N×100米处）。教主为了想收集能量，想跳着吃完所有的能量球。教主可以自由控制他每次跳的高度，接着他跳起把这个高度以下的能量球都吃了，他便能获得能量球内的能量，接着吃到的能量球消失。教主不会轻功，教主不会二段跳，所以教主不能因新吃到的能量而变化此次跳跃的高度。并且教主还是生活在地球上的，所以教主每次跳完都会掉下来。

  • 问教主若要吃完所有的能量球，最多还能保留多少能量。

输入：

  1. 第1行包含两个正整数N，M，表示了能量球的个数和LHX教主的初始能量。
  2. 第2行包含N个非负整数，从左到右第I个数字依次从下向上描述了位于I×100米位置能量球包含

输出：

仅包括一个非负整数，为教主吃完所有能量球后最多保留的能量。

题解：

这道题……也是挺强的，是一道单调性优化的入门级题目QAQ

我们设置一下状态f[i]表示的是最后一次跳跃能吃到第i个能量球之后所能保留的最大能量，其中进行一下预处理a[i]表示前i个能量球的前缀和，然后列出状态转移方程：

1
f[i]=max(f[i],f[j]+a[i]-a[j]-100*i)

状态转移方程列出来之后，我们发现还是无法解决这道题，毕竟200w的数据范围双重循环你还是想太多了，那么怎么才能优化成O(N)级别的算法呢，降低状态设置的维度吗？少年这是不可能的，都是一维了怎么降，那么我们只能从寻找最优值开始想办法，在O(1)的时间里面找到f[i]的最优值。

那么我们就开始将方程进行一个小小的变形吧！

1
f[i]=max(f[i],(f[j]-a[j])-100*i)

看到了扩号里面的内容了吗，在这个方程中，只有加粗的内容是不确定的，是需要用一维枚举来的出来的，那么能O(1)解决吗？如果我们能够直接得出f[j]-a[j]的最大值，那是不是直接加上去就好了，根本不需要找。

我们可以用一个单调队列来存下来最优的f[j]-a[j]的最优值，因为是单调队列，所以队头的元素就是最优值，之所以用队列进行存储的原因就是因为可能你现在有的能量，也就是f[j]不足以支持你跳跃到i这个位置，所以说需要用队列不断的淘汰不合法的值并且更新更优的值。

更新的时候在队尾用while来更新，因为可能有多个值可以被更新掉，更新队头的时候也用while来淘汰不合法的值。

代码：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iomanip>
#include<cmath>
using namespace std;
int n,m,a[2000001],f[2000001];
int This,ans=0,Line[2000001],Start=1,End=1;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    Line[Start]=0;
    f[0]=m; a[0]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
    for(int i=1;i<=n;i++)
    {
        while(f[Line[Start]]<100*i&&Start<End) Start++;
        f[i]=f[Line[Start]]+a[i]-a[Line[Start]]-i*100;
        if(f[i]-a[i]>f[Line[End]]-a[Line[End]])
        while(f[i]-a[i]>f[Line[End]]-f[Line[End]]) End--;
        Line[++End]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}

P1327HAOI订货

题目描述：

某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S；

输入：

  1. 第1行：n,m,S (0<=n<=50,0<=m<=10,0<=S<=10000)
  2. 第2行：U1,U2,…,Ui,…,Un (0<=Ui<=10000)
  3. 第3行：d1,d2,…,di,…,dn (0<=di<=100)

输出：

只有1行，一个整数，代表最低成本；

题解：

这道题其实也是不错的题，但是网上大多人都说这是一道网络流的裸体，十几分钟敲完QAQ，这可是HA省省选啊，怎么可以弱成这个样子！结果自己式用DP加上单调性优化过去的。

我们设置状态 f[i][j] 表示第i个月存储数量为j货物所需要的最小成本，和往常一样，列出来他的状态转移方程：

1
f[i][j]=min(f[i][j],f[i-1][k]+(u[i]+j-k)*d[i]+m*k);

相信这个转移方程还是很好理解的说，然后我们和上面的那道题一模一样，将这个可爱的方程小小的变形一下。把不确定的量列在一起，确定的放在一边不管；

1
f[i][j]=min(f[i][j],(f[i-1][k]+(m-d[i])*k)+(u[i]+j)*d[i]);

现在是不是有些思路了，没错我们需要保证 (f[i-1][k]+(m-d[i])*k) 这个是最小的就好了，那么我们就单独的用一个ans来记录下来最小的值（因为队头不会因为不合法的原因被淘汰掉，所以每次只需要保留最优值）。每次找出在 min(u[i]+j,S) 之前的 f[i-1][k] 的最优值赋给 ans 就好了。

代码：

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,Price,S,f[100][10001];
int Pay[100],Need[100],ans;
int main()
{
    cin>>n>>Price>>S;
    for(int i=1;i<=n;i++) cin>>Need[i];
    for(int i=1;i<=n;i++) cin>>Pay[i];
    for(int i=1;i<=S;i++) f[0][i]=123456789;
    for(int i=1;i<=n;i++)
    {
        int k=0,ans=123456789;
        for(int j=0;j<=S;j++)
        {
            for(;k<=min(Need[i]+j,S);k++)
            ans=min(ans,f[i-1][k]+k*(Price-Pay[i]));
            f[i][j]=ans+(Need[i]+j)*Pay[i];
        }
    }
    cout<<f[n][0]<<endl;
    return 0;
}

后话

关于单调性优化的题目就到这里了，感谢闵神的讲稿，很详细，写的很认真，看起来比较通俗易懂，而且注重思维的引导！

DP离散化

P1309过河

题目描述：

  • 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
  • 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。对于30%的数据，L <= 10000；对于全部的数据，L <= 10^9。

输入：

输入的第一行有一个正整数L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出：

输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。

题解：

首先我们看完题，差不多状态转移方程都是能列出来的，我们设f[i]表示到达坐标i的时候踩到的最小石子数量，然后每次跟新的时候从前面能到达的地方开始寻找，大概是从i-max_jump到i-min_jump这个范围，然后找出最少的一个，然后验证，如果这个坐标是有石子的+1；

那么很简单，但是看题目10^9的范围，虽然是不纯粹的二重循环，但是还是要超时的。那么我们能不能在10^9上面做文章。

离散化的思想就是保留下来自己需要的，不需要的进行抛弃，那么我们需要的是什么？题目中的石子数量最大也不过是100，也就是说M<<L的，所以说我们需要的是M，两个M之间很长很长的一部分是完全不需要的，我们就可以抛弃这些，但是问题是抛弃哪些呢？

我们在第一个点，开始向2,3,4,5…….这些跳跃的时候，有些是不可能达不到的，有些是肯定能达到的，那么是哪些不可能达到，哪些必定能达到呢。举一下例子吧，其中1表示可以到达，0表示不能达到，第几个数表示坐标。

当跳跃范围是3-4的时候：1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1……

当跳跃范围是2-4的时候：1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1……

当跳跃范围是4-5的时候：1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1……

没错，规律就是这样，在minmax之后的点是必定能到达的（其实并不精确，但是这句话一定是成立的），具体证明并不会，但是不妨碍做题。也就是说如果距离大于minmax的时候，我们就可以把他们缩减到min*max，这样就可以避免很多不必要的坐标计算。

还有，记得有一种情况就是max等于min的时候，这种时候需要单独处理。

代码：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int Brige,Max_long,Min_long,n,m;
int a[201],b[201],f[1000001],ans=100;
bool Get[10000001],Arrived[10000001];
long long The_max;
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(f,0,sizeof(f));
    memset(Get,false,sizeof(Get));
    memset(Arrived,false,sizeof(Arrived));
    cin>>Brige>>Min_long>>Max_long>>n;
    a[n+1]=Brige;
    Arrived[0]=true;
    Brige=Max_long*Min_long;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n+1;i++)
    {
        if(a[i]-a[i-1]>Brige)
        b[i]=b[i-1]+Max_long+1;
        else b[i]=b[i-1]+a[i]-a[i-1];
        if(i==n+1) continue;
        else Get[b[i]]=true;
    }
    Brige=b[n+1];
    if(Max_long==Min_long)
    {
        int all=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]%Max_long==0)
            all++;
        }
        cout<<all<<endl;
        return 0;
    }
    for(int i=Min_long;i<=Brige+Max_long-1;i++)
    {
        f[i]=f[i-1];
        for(int j=Min_long;j<=Max_long;j++)
        if(Arrived[i-j]==true)
        {
            f[i]=min(f[i],f[i-j]);
            Arrived[i]=true;
        }
        if(Get[i]==true) f[i]++;
    }
    for(int i=Brige;i<=Brige+Max_long-1;i++)
    ans=min(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}