P3097 [USACO13DEC]最优挤奶（线段树优化dp）

盲猜dp系列。。。

题意：给定序列，选了i就不能选与i相邻的两个，求最大值，带修改

蒟蒻在考场上10min打完以为只有两种情况的错解。。。居然能骗一点分。。。

先讲下当时的思路吧。

f【i】【0/1】表示第i台选不选的挤奶最大值，两个转移，水得不行。

考完之后在大佬的点播下才明白，这是一个类似独立集的东西。

但是这个数据范围绝对不是让我们跑最大独立集的，毕竟还要修改233。。。

solution：

求和....单点修改...最大值....貌似能想到些什么.....

可爱的线段树。。（一点都不可爱）

毕竟序列长不变，只要单点修改就行了。

建一棵线段树，里面存f1，f2，f3，f4，l，r；

// f1 表示两端都选 // f2 表示左选右不选 // f3 表示左不选右选 // f4 表示左右都不选

然后转移就比较长，其它也没有什么（应该能看明白就懒得写注释了）

void update(ll k)

{

    t[k].f1=max(t[lch(k)].f1+t[rch(k)].f3,t[lch(k)].f2+max(t[rch(k)].f1,t[rch(k)].f3));

    t[k].f2=max(t[lch(k)].f1+t[rch(k)].f4,t[lch(k)].f2+max(t[rch(k)].f2,t[rch(k)].f4));

    t[k].f3=max(t[lch(k)].f3+t[rch(k)].f3,t[lch(k)].f4+max(t[rch(k)].f1,t[rch(k)].f3));

    t[k].f4=max(t[lch(k)].f3+t[rch(k)].f4,t[lch(k)].f4+max(t[rch(k)].f2,t[rch(k)].f4));

}

然后就是线段树的事了

代码：

#include<bits/stdc++.h>

#define lch(x) x<<1

#define rch(x) x<<1|1

#define ll long long

using namespace std;

const ll maxn=1e6+;

ll a[maxn];

ll n,d;

ll ans;

struct tree

{

    ll f1,f2,f3,f4;

    ll l,r;

}t[maxn];

ll p,v;

void update(ll k)

{

    t[k].f1=max(t[lch(k)].f1+t[rch(k)].f3,t[lch(k)].f2+max(t[rch(k)].f1,t[rch(k)].f3));

    t[k].f2=max(t[lch(k)].f1+t[rch(k)].f4,t[lch(k)].f2+max(t[rch(k)].f2,t[rch(k)].f4));

    t[k].f3=max(t[lch(k)].f3+t[rch(k)].f3,t[lch(k)].f4+max(t[rch(k)].f1,t[rch(k)].f3));

    t[k].f4=max(t[lch(k)].f3+t[rch(k)].f4,t[lch(k)].f4+max(t[rch(k)].f2,t[rch(k)].f4));

}

void build(ll l,ll r,ll p)

{

    t[p].l=l;

    t[p].r=r;

    if(l==r)

    {

        t[p].f1=a[l];

        return;

    }

    ll mid=l+r>>;

    build(l,mid,p<<);

    build(mid+,r,p<<|);

    update(p);

}

void change(ll k)

{

    if(t[k].l==t[k].r)

    {

        t[k].f1=v;

        return;

    }

    ll mid=(t[k].l+t[k].r)>>;

    if(p<=mid)change(k<<);

    else change(k<<|);

    update(k);

}

int main()

{

    scanf("%lld%lld",&n,&d);

    for(ll i=;i<=n;i++)

    {

        scanf("%lld",&a[i]);

    }

    build(,n,);

    for(ll i=;i<=d;i++)

    {

        scanf("%lld%lld",&p,&v);

        change();

        ans+=max(max(t[].f1,t[].f2),max(t[].f3,t[].f4));

    }

    printf("%lld",ans);

    return ;

}

（完）

巴特西

P3097 [USACO13DEC]最优挤奶（线段树优化dp）

最新文章

热门文章