题解 P3097 【[USACO13DEC]Optimal Milking G】

· · 题解

来补一个动态 dp 做法。

题意大致就是单点修改求最大独立集

暴力 dp 大概就是

\begin{cases} f_{i,0}=\max\limits \{ f_{i-1,0},f_{i-1,1}\} \\ f_{i,1}=f_{i-1,0}+a_i \end{cases}

最后是要求 \max\{ f_{n,0},f_{n,1} \}

考虑这个东西怎么转为矩阵形式。

这里我们定义矩阵乘法为

c_{i,j}=\max\limits_{k} \{ a_{i,k}+b_{k,j} \}

这个东西是满足结合律的。

于是上面那个暴力 dp 可以看成是

\begin{bmatrix}f_{i-1,0}\\ f_{i-1,1}\end{bmatrix} \begin{bmatrix}0 \ \ \ \ \ 0 \\ a_i\ \operatorname{-inf} \end{bmatrix}= \begin{bmatrix} f_{i,0} \\f_{i,1} \end{bmatrix}

然后用线段树维护矩阵乘即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
const int N=40000+5;
// f[i][0]=max(f[i-1][0],f[i-1][1])
// f[i][1]=f[i-1][0]+a[i]
// |  0 0      |  
// |  a_i -inf |
struct mat{
    int a[2][2];
    mat(){
        memset(a,-0x3f,sizeof(a));
    }
    mat operator *(const mat &b) const{
        mat res;
        for(int i=0;i<2;++i)
            for(int j=0;j<2;++j)
                for(int k=0;k<2;++k)
                    res.a[i][j]=max(res.a[i][j],a[i][k]+b.a[k][j]);
        return res;
    }
}tr[N<<2];
int a[N];
void pushup(int p){
    tr[p]=tr[rs]*tr[ls];
}
void build(int p,int l,int r){
    if(l==r){
        tr[p].a[0][0]=0;
        tr[p].a[0][1]=0;
        tr[p].a[1][0]=a[l];
        tr[p].a[1][1]=-0x3f3f3f3f;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(p);
}
void upt(int p,int l,int r,int pos,int v){
    if(l==r){
        tr[p].a[0][0]=0;
        tr[p].a[0][1]=0;
        tr[p].a[1][0]=v;
        tr[p].a[1][1]=-0x3f3f3f3f;
        return;     
    }
    int mid=(l+r)>>1;
    if(pos<=mid) upt(ls,l,mid,pos,v);
    else upt(rs,mid+1,r,pos,v);
    pushup(p);
}
int main(){
    long long ans=0;
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    int pos,v;
    build(1,1,n);
    mat res,tmp;
    res.a[0][0]=0;res.a[0][1]=0;
    while(q--){
        cin>>pos>>v;
        upt(1,1,n,pos,v);
        tmp=res*tr[1];
        ans+=max(tmp.a[0][0],tmp.a[0][1]);
        //cout<<max(tmp.a[0][0],tmp.a[0][1])<<endl;
    }
    cout<<ans;
    return 0;
}