Loading...

动态dp 学习笔记

check评论:0 条 remove_red_eye浏览量:397 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-02-23

动态$dp$可真可爱

首先用最大子段和问题来说,大家都会

但是如果带修改,求区间最大子段和呢?

我们考虑一下最大字段和里的$dp$数组

$f[i]=max(f[i-1]+a[i],a[i]);\ g[i]=max(g[i-1],f[i]);$

我们将其写成矩阵乘法形式

$\left\{\begin{matrix} {a[i]}&{- \infty}&{a[i]}\\{a[i]}&{0}&{a[i]}\\{- \infty}&{- \infty}&{0}\end{matrix}\right\}\times \left\{\begin{matrix}f[i-1]\\g[i-1]\\0\end{matrix}\right\}=\left\{\begin{matrix}f[i]\\g[i]\\0\end{matrix}\right\}$

然后线段树维护每个区间的矩阵乘积就可以做到总时间$nlogn$复杂度了

例题:SP1716 GSS3

code:

#include <bits/stdc++.h>
using namespace std;
struct matrix
{
    int data[3][3];
    void set(int x)
    {
        data[0][0]=data[1][0]=data[0][2]=data[1][2]=x;
        data[0][1]=data[2][0]=data[2][1]=-0x3f3f3f3f;
        data[2][2]=data[1][1]=0;
    }
    void clear()
    {
        for(int i=0;i<=2;i++)
        {
            for(int j=0;j<=2;j++)
            {
                data[i][j]=-0x3f3f3f3f;
            }
        }
    }
}mat[400010];
int a[100010],n;
matrix mul(matrix a,matrix b)
{
    matrix c;
    c.clear();
    for(int k=0;k<=2;k++)
    {
        for(int i=0;i<=2;i++)
        {
            for(int j=0;j<=2;j++)
            {
                c.data[i][j]=max(c.data[i][j],a.data[i][k]+b.data[k][j]);
            }
        }
    }
    return c;
}
#define pushup(o) mat[o]=mul(mat[o<<1],mat[o<<1|1])
void build(int o,int lf,int rg)
{
    if(lf==rg)
    {
        mat[o].set(a[lf]);
        return ;
    }
    int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
void modify(int o,int lf,int rg,int w,int x)
{
    if(lf==rg)
    {
        mat[o].set(x);
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        modify(o<<1,lf,mid,w,x);
    }
    if(mid<w)
    {
        modify(o<<1|1,mid+1,rg,w,x);
    }
    pushup(o);
}
matrix query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return mat[o];
    }
    int mid=(lf+rg)>>1;
    if(l<=mid&&mid<r)
    {
        return mul(query(o<<1,lf,mid,l,r),query(o<<1|1,mid+1,rg,l,r));
    }
    else if(l<=mid)
    {
        return query(o<<1,lf,mid,l,r);
    }
    else if(mid<r)
    {
        return query(o<<1|1,mid+1,rg,l,r);
    }
}
int main()
{
     cin>>n;
     for(int i=1;i<=n;i++)
     {
         scanf("%d",&a[i]);
     }
     build(1,1,n);
     int q;
     cin>>q;
     for(int i=1;i<=q;i++)
     {
         int opt,x,y;
         scanf("%d%d%d",&opt,&x,&y);
         if(opt==0)
         {
             modify(1,1,n,x,y);
         }
         else
         {
             matrix a=query(1,1,n,x,y);
            printf("%d\n",max(a.data[1][0],a.data[1][2])); 
         }
     }
}

(EX)bsgs 学习笔记 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名