先看下面一道题：

将一个序列划分为若干个连续子序列，每个子序列的权值是它们和与常数 L 的差的平方。求所有子序列的权值和最小是多少？

思路：

最简单的思路是：$f[i]=min(f[j]+(sum[i]-sum[j]-L)^2)$
于是我们就可以在 $O(n^2)$时间内求解。
但是，能不能更快一些呢？
下面，就介绍如何优化 Dp 的基本方法之一：证明决策单调性

如何证明决策单调性

方法一：（最简单实用的）打表

有很多 Dp 状态转移方程都有决策单调性。其中一种为：

　对于状态 i 和 j, 它们分别从 s[i] 和 s[j] 转移过来。那么这一类题目满足以下规律：$s[i]\textless=s[j](i\textless j)$

这种规律常常隐藏在复杂或者奇怪的状态转移方程中。想要证明它们的单调性及其复杂，限制也多。所以我们不妨直接用数学归纳法得出这种规律。

以 “玩具装箱 BZOj1010” 为例

设序列 C，将其分为若干个连续子序列，若子序列起点为 j，终点为 i，L 为一给定常数，那么每个序列的权值是这么计算的：
$$(j-i+Sigma(Ck)-L)^2(j\textless=k\textless=i)$$
这道题的转移方程和例题很像，直接写出：$f[i]=min(f[j]+(i-j+sum[i]-sum[j]-L)^2)$
然后我们就有一个很垃圾的程序：我们写出它的目的是为了记录 s 数组，也就是对于每个状态 i，它是由哪个状态 s[i] 转移过来的。

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 100010

using namespace std;

int f[MX],s[MX],seq[MX],n,L, sum[MX];

void input()
{
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++)scanf("%d",&seq[i]);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+seq[i];
}

void work()
{
    for(int i=1;i<=n;i++)
    {
        f[i]=99999999;
        for(int j=0;j<i;j++)
            if(f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L)<f[i])
                f[i]=f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L),s[i]=j;
    }
    cout<<f[n]<<endl;
    for(int i=1;i<=n;i++)cout<<s[i]<<" ";
}

int main()
{
    input();
    work();
    return 0;
}

然后我们发现，对于任意的随机数据，s[i] 都是不降的。所以我们可以猜想：对于所有数据，s[i] 都是不降的。
利用这个猜想，我们就可以将复杂度优化为 O(n)~O(n²)(我猜可能是 $O(n\frac{Ln}{\sum a[i]}) 左右 $)，下面这份代码就可以 AC 了。虽然它依旧没有斜率优化的 O(n) 来地猛，但是至少可以通过哈哈。

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 100010

using namespace std;
typedef long long ll;

int s[MX];
ll n,L,sum[MX],seq[MX],f[MX];

void input()
{
    scanf("%lld%lld",&n,&L);
    for(int i=1;i<=n;i++)scanf("%lld",&seq[i]);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+seq[i];
}

void work()
{
    int j;
    s[0]=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=999999999999999;
        for(j=s[i-1];j<i;j++)
            if(f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L)<f[i])
                f[i]=f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L),s[i]=j;
    }
    cout<<f[n]<<endl;
}

int main()
{
    input();
    work();
    return 0;
}

方法二：数学证明：

还是以 “玩具装箱 BZOj1010” 为例
假设在状态 i 处的 k 决策优与 j 决策，即
$$dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2$$

则对于 i 后的所有状态 t，要证明决策单调性即
$$dp[k]+(f[t]-f[k]-c)^2<=dp[j]+(f[t]-f[j]-c)^2$$

只要证
$$dp[k]+(f[i]+v-f[k]-c)^2<=dp[j]+(f[i]+v-f[j]-c)^2$$

将上面两个式子相减得：
$$2v(f[i]-f[k]-c)<=2v(f[i]-f[j]-c)$$

即
$$f[k]>=f[j]$$

证明完毕
这个证明了神码呢？就是对于 i 和 i+v 这两个状态，i+v 的最优决策一定在 i 的最优决策和 [i,i+v-1] 这个区间中。因为决策单调性告诉我们，以前状态的各个决策之间的优劣是相对固定的。所以原来的劣解一定不会成为最优决策。因此就减小了决策范围。消除不必要的状态，就是一种优化。