DP

斜率优化

只凸不凹

Posted by JU on July 20, 2018

注意

在将分母乘到另一边去的时候，注意正负性，尽量保证分母为正。

Luogu4072

\[a=\frac {\sum_{i=1}^{m}v_i}{m}\] \[s^{2}=\frac {\sum_{i=1}^{m}(a-v_i)^2}{m}\] \[=\frac {\sum_{i=1}^{m}(a^2-2av_i+v_i^2)}{m}\] \[=\frac{m·a^2-2a·\sum_{i=1}^{m}v_i+\sum_{i=1}^{m}v_i^2}{m}\] \[ans=s^2·m^2=(\sum_{i=1}^{m}v_i)^2-2·(\sum_{i=1}^{m}v_i)^2+m·\sum_{i=1}^{m}v_i^2\] \[=-(\sum_{i=1}^{m}v_i)^2+m·\sum_{i=1}^{m}v_i^2\] \[=m·\sum_{i=1}^{m}v_i^2-(\sum_{i=1}^{n}a_i)^2\] \[=m·\sum_{i=1}^{m}v_i^2-SUM^2\] \[f[i][l]\]

前i段路花了前l天来走的花费除以m

\[ans=f[n][m]·m-SUM^2\] \[f[i][l]=min_{j=1}^{i-1}\{f[j][l-1]+(sum[i]-sum[j])^2\}\]

设j1<j2且j2优于j1

\[f[j1][l-1]+(sum[i]-sum[j1])^2>f[j2][l-1]+(sum[i]-sum[j2])^2\] \[f[j1][l-1]+(sum[i]^2-2sum[i]sum[j1]+sum[j1]^2)>f[j2][l-1]+(sum[i]^2-2sum[i]sum[j2]+sum[j2]^2)\] \[(sum[i]^2-2sum[i]sum[j1]+sum[j1]^2)-(sum[i]^2-2sum[i]sum[j2]+sum[j2]^2)>f[j2][l-1]-f[j1][l-1]\] \[sum[j1]^2-sum[j2]^2+2sum[i](sum[j2]-sum[j1])>f[j2][l-1]-f[j1][l-1]\] \[2sum[i](sum[j2]-sum[j1])>f[j2][l-1]-f[j1][l-1]+sum[j2]^2-sum[j1]^2\] \[\frac{f[j2][l-1]-f[j1][l-1]+sum[j2]^2-sum[j1]^2}{(sum[j2]-sum[j1])}<2sum[i]\]

下凸壳（注意jj1,jj2,jj3是从右到左排列的）

jj1,jj2,jj3中,jj2最菜

\[\frac{f[jj2][l-1]-f[jj1][l-1]+sum[jj2]^2-sum[jj1]^2}{(sum[jj2]-sum[jj1])}<=\frac{f[jj3][l-1]-f[jj2][l-1]+sum[jj3]^2-sum[jj2]^2}{(sum[jj3]-sum[jj2])}\] 
#include <bits/stdc++.h>
#define pr(p) printf("%lld\n",p)
const int oo=2139063143;
const int N=3100;
const int mod=1000000007;
using namespace std;
typedef long long LL;
inline void sc (LL &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
LL a[N],sum[N];
LL f[N][N];
LL q[N],head,tail;
#define j1 q[head]
#define j2 q[head+1]
#define jj1 i
#define jj2 q[tail]
#define jj3 q[tail-1]
LL S(LL a) { return a*a; }
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    LL n,m; sc(n),sc(m);
    for (LL i=1; i<=n; i++)
        sc(a[i]),sum[i]=sum[i-1]+a[i],f[i][1]=S(sum[i]);

    for (LL l=2; l<=m; l++)
    {
        head=1,tail=0;
        for (LL i=1; i<=n; i++)
        {
            while (head< tail&&f[j2][l-1]-f[j1][l-1]+S(sum[j2])-S(sum[j1])<=2*sum[i]*(sum[j2]-sum[j1])) ++head;
            f[i][l]=f[j1][l-1]+S(sum[i]-sum[j1]);
            while (head< tail&&(f[jj2][l-1]-f[jj1][l-1]+S(sum[jj2])-S(sum[jj1]))*(sum[jj3]-sum[jj2])<=
                               (f[jj3][l-1]-f[jj2][l-1]+S(sum[jj3])-S(sum[jj2]))*(sum[jj2]-sum[jj1])) --tail;
            q[++tail]=i;
        }
        memset (q,0,sizeof (q));
    }
    pr(m*f[n][m]-S(sum[n]));
    return 0;
}

Luogu2900

#include <bits/stdc++.h>
#define sc(p) scanf("%lld",&p)
#define sc2(p1,p2) scanf("%lld%lld",&p1,&p2)
#define sc3(p1,p2,p3) scanf("%d%d%d",&p1,&p2,&p3)
#define pr(p) printf("%d\n",p)
const int oo=2147483640;
const int N=1010000;
const int mod=1000000007;
using namespace std;
struct MUD { long long h,w; }sb[N];
bool ly (MUD A,MUD B) { return A.h>B.h; }
long long x[N],y[N],f[N];
long long q[N],head,tail;
#define j1 q[head]
#define j2 q[head+1]
#define jj1 i
#define jj2 q[tail-1]
#define jj3 q[tail-2]
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    long long n; sc(n);
    for (int i=1; i<=n; i++) sc2(sb[i].h,sb[i].w);
    sort (sb+1,sb+n+1,ly);
    int ma=0,tot=0;
    for (int i=1; i<=n; i++)
    {
        if (sb[i].w<=ma) continue;
        x[++tot]=sb[i].w; y[tot]=sb[i].h;
        ma=x[tot];
    }
    n=tot;
    q[0]=0,head=0,tail=1;
    for (int i=1; i<=n; i++)
    {

        while (head+1<tail&& f[j2]-f[j1] <= x[i]*(y[j1+1]-y[j2+1]))
        head++;
        f[i]=f[j1]+x[i]*y[j1+1];
        while (head+1<tail&& (f[jj2]-f[jj1])*(y[jj2+1]-y[jj3+1]) <= 
                             (f[jj3]-f[jj2])*(y[jj1+1]-y[jj2+1])) tail--;
        q[tail++]=i;
        //cout<<f[i]<<" "; 
    }
    cout<<f[n];
    return 0;
}

斜率优化

概念

用于优化形如\(f[i]=max \left\{ f[j]+g[i]*x[j]+t[j]+h[i] \right\}\)的DP转移方程。

BZOJ3437

首先设f[i]表示在第i个位置建站的最小花费。
列出状态转移方程：\(f[i]=min\{f[j]+ \sum_{k=j+1}^i (i-k)b[k]+a[i]\}\)
拆开Sigma得到\(i \sum_{k=j+1}^i b[k] - \sum_{k=j+1}^i k*b[k]\)
再拆成两个部分和\(sum1[i]=\sum_{k=1}^i\)、\(sum1[i]=\sum_{k=1}^i k*b[k]\)
最后的形式为\(f[i]=min\{f[j]+sum2[j]-i*sum1[j]+i*sum1[i]-sum2[i]+a[i]\}\)

重点1：设j1<j2，且j2优于j1。

易得\(f[j1]+sum2[j1]-i*sum1[j1]>f[j2]+sum2[j2]-i*sum1[j2]\)
设fs[i]=f[i]+sum2[i]
代入并变形得\(i(sum1[j2]-sum1[j1])>fs[j2]-fs[j1]\)
再变形得\(i> \frac{fs[j2]-fs[j1]}{sum1[j2]-sum1[j1]}\)
将其视为用两点表示直线的斜率，斜率优化由此得名。

双端队列

每次枚举到一个i，就将其与队列首用上述规则比较，弹出部分不优的候选，计算i的答案。

重点2

设j1、j2、j3为连续三点，k1、k2为相邻两点连线斜率。当k1>k2，分类讨论易得j2无用，将其从队尾弹出。
弹完后，队尾插入i。

程序

#include <bits/stdc++.h>
#define sc(p) scanf("%lld",&p)
#define pr(p) printf("%d\n",p)
const int N=1010000;
using namespace std;
long long a[N],b[N];
long long sum1[N]={0},sum2[N]={0},f[N]={0},fs[N];
int q[N],head,tail;
#define j1 q[head]
#define j2 q[head+1]
#define jj1 i
#define jj2 q[tail-1]
#define jj3 q[tail-2] 
int main()
{
    int n; sc(n);
    for (int i=1; i<=n; i++) sc(a[i]);
    for (int i=1; i<=n; i++) sc(b[i]),sum1[i]=sum1[i-1]+b[i],sum2[i]=sum2[i-1]+i*b[i];
    q[0]=0,head=0,tail=1;
    for (int i=1; i<=n; i++)
    {
        while (head+1<tail&&fs[j2]-fs[j1]<=i*(sum1[j2]-sum1[j1]))    head++;

        f[i]=f[j1]+sum2[j1]-i*sum1[j1]+i*sum1[i]-sum2[i]+a[i];
        fs[i]=f[i]+sum2[i];

        while (head+1<tail&&(fs[jj2]-fs[jj1])*(sum1[jj3]-sum1[jj2]) <=
                            (fs[jj3]-fs[jj2])*(sum1[jj2]-sum1[jj1])) tail--;
        q[tail++]=i;
    }
    cout<<f[n];
    return 0;
}

滋磁

%%%罗梓璋 来自罗指导ppt

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：斜率优化”
CATALOG
    FRIENDS