先看下面一道题:

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

分类: 所有

2 条评论

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

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

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

    现在没有问题了

发表评论

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

你是机器人吗? =。= *