先看下面一道题:

将一个序列划分为若干个连续子序列,每个子序列的权值是它们和与常数 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(n2)(我猜可能是 $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] 这个区间中。因为决策单调性告诉我们,以前状态的各个决策之间的优劣是相对固定的。所以原来的劣解一定不会成为最优决策。因此就减小了决策范围。消除不必要的状态,就是一种优化。

分类: 文章

5 条评论

konnyakuxzy · 2017年7月17日 1:07 下午

完了,出现了一个问题:公式太长了显示不出来。。。
可以自行右键公式->查看图像解决该问题

    boshi · 2017年7月18日 8:02 上午

    现在没有问题了

      mayday · 2023年1月1日 5:10 下午

      好像还是有问题 加载不出来

        Qiuly · 2023年1月2日 8:09 上午

        具体是哪里的问题啊 /kel

          mayday · 2023年1月2日 9:55 上午

          方法一的数学公式显示不了

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注