动态DP

Posted on   |   In ,

前言

动态DP????

难道是传说中会动的DP??? 但是据我们所知DP状态都定了 还能改变吗???

动态DP:就是DP上进行一些单点修改操作

参考博客

需要相应较强的数据结构的前置知识点和普通的DP能力(因为你发现整个过程都是再用一些数据结构在维护)

例题

SP1716 GSS3 - Can you answer these queries III

题意:

​ $n$个数,$q$次操作

  • 操作$0 x y$ 把$A_x$修改成$y$
  • 操作$1lr$询问区间$[l,r]$的最大子段和

题解:

直接考虑线段树区间合并即可,不需要动态DP

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
const int inf=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}


int lmax[MAXN<<2],rmax[MAXN<<2],sum[MAXN<<2],maxx[MAXN<<2];
int a[MAXN];
void up(int x,int l,int r){
    maxx[x]=max(maxx[l],maxx[r]);
    maxx[x]=max(maxx[x],rmax[l]+lmax[r]);
    lmax[x]=max(lmax[l],sum[l]+lmax[r]);
    rmax[x]=max(rmax[r],sum[r]+rmax[l]);
    sum[x]=sum[l]+sum[r];
}

void built(int x,int l,int r){
    if(l==r){lmax[x]=rmax[x]=sum[x]=maxx[x]=a[l];return ;}
    int mid=(l+r)>>1;
    built(x<<1,l,mid);built(x<<1|1,mid+1,r);
    up(x,x<<1,x<<1|1);
}

void update(int x,int l,int r,int t,int k){
    if(l==r){lmax[x]=rmax[x]=sum[x]=maxx[x]=k;return ;}
    int mid=(l+r)>>1;
    if(t<=mid)update(x<<1,l,mid,t,k);
    else update(x<<1|1,mid+1,r,t,k);
    up(x,x<<1,x<<1|1);
}

int ans;bool flag=0;
void copy(int x,int y){
    lmax[x]=lmax[y];rmax[x]=rmax[y];sum[x]=sum[y];maxx[x]=maxx[y];
}
void query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
    if(!flag)copy(ans,x);
    else up(ans,ans,x);
    flag=1;
    return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(x<<1,l,mid,ql,qr);
    if(qr>mid)query(x<<1|1,mid+1,r,ql,qr);
}
int n;
int main(){
    n=read();
    inc(i,1,n)a[i]=read();
    built(1,1,n);
    int q=read();
    int op,x,y;
    ans=0;
    while(q--){
    op=read();x=read();y=read();
    if(op==0)update(1,1,n,x,y);
    else{
        flag=0;query(1,1,n,x,y);
        printf("%d\n",maxx[ans]);
    }
    }
    return 0;
}

P4719 动态DP

题意:

给定一棵$n$个点的树，点带点权。

有$m$次操作，每次操作给定$x,y$，表示修改点$x$的权值为$y$。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

题解:

考虑不带修的情况 写出DP递推式转化成矩阵形式

然后发现具有结合律 我们用LCT来维护矩阵

复杂度 $O(8*nlogn)$

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
const int inf=1e9+9;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

typedef struct Matrix{
    int num[3][3];
    void init(int x){
    num[0][0]=num[0][1]=0;num[1][0]=x;num[1][1]=-inf;
    }
    Matrix operator*(const Matrix &v){
    Matrix ans;
    inc(i,0,1)inc(j,0,1)ans.num[i][j]=-inf;
    for(int k=0;k<=1;k++){
        for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            ans.num[i][j]=max(ans.num[i][j],num[i][k]+v.num[k][j]);
        }
        }
    }
    return ans;
    }
}Matrix;

int ch[MAXN][2],pre[MAXN],a[MAXN];
Matrix p[MAXN],s[MAXN];
bool rt[MAXN];

void newnode(int x,int y){
    ch[x][0]=0;ch[x][1]=0;rt[x]=1;pre[x]=0;
    p[x].init(y);s[x].init(-inf);
}
void up(int x){
    s[x]=p[x];
    if(ch[x][0])s[x]=s[ch[x][0]]*s[x];
    if(ch[x][1])s[x]=s[x]*s[ch[x][1]];
    //cout<<x<<":::::::"<<s[x].num[0][0]<<" "<<s[x].num[1][0]<<endl;
}
void rotate(int x,int kind){
    int y=pre[x];
    pre[ch[x][kind]]=y;ch[y][!kind]=ch[x][kind];
    if(rt[y])rt[x]=1,rt[y]=0;
    else ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;
    up(y);
}
void splay(int x){
    while(!rt[x]){
    if(rt[pre[x]])rotate(x,ch[pre[x]][0]==x);
    else{
        int y=pre[x];int kind=ch[pre[y]][0]==y;
        if(ch[y][kind]==x)rotate(x,!kind),rotate(x,kind);
        else rotate(y,kind),rotate(x,kind);
    }
    }
    up(x);
}
void access(int x){
    int y=0;
    while(x){
    splay(x);
    if(ch[x][1]){
        rt[ch[x][1]]=1;pre[ch[x][1]]=x;
        p[x].num[0][0]+=max(s[ch[x][1]].num[0][0],s[ch[x][1]].num[1][0]);
        p[x].num[0][1]+=max(s[ch[x][1]].num[0][0],s[ch[x][1]].num[1][0]);
        p[x].num[1][0]+=s[ch[x][1]].num[0][0];
    }
    if(y){
        rt[y]=0;
        p[x].num[0][0]-=max(s[y].num[0][0],s[y].num[1][0]);
        p[x].num[0][1]-=max(s[y].num[0][0],s[y].num[1][0]);
        p[x].num[1][0]-=s[y].num[0][0];
    }
    ch[x][1]=y;up(x);
    y=x;x=pre[x];
    }
}
void join(int x,int y){
    p[y].num[0][0]+=max(p[x].num[0][0],p[x].num[1][0]);
    p[y].num[0][1]+=max(p[x].num[0][0],p[x].num[1][0]);
    p[y].num[1][0]+=p[x].num[0][0];
}
void dfs(int x,int y){
    link(x){
    if(y==j->t)continue;
    dfs(j->t,x);
    join(j->t,x);pre[j->t]=x;
    }
    //cout<<x<<" "<<p[x].num[0][0]<<" "<<p[x].num[1][0]<<endl;
}
int n,m;
int main(){
    //s[0].num[0][0]=s[0].num[0][1]=0;s[0].num[1][0]=-inf;s[0].num[1][1]=-inf;
    int x,y;
    n=read();m=read();
    inc(i,1,n){
    a[i]=read();newnode(i,a[i]);
    }
    inc(i,2,n){
    x=read();y=read();
    add(x,y);add(y,x);
    }
    dfs(1,0);
    //cout<<" "<<s[1].num[0][0]<<":::"<<s[1].num[1][0]<<endl;
    while(m--){
    x=read();y=read();
    access(x);splay(x);
    p[x].num[1][0]+=(y-a[x]);a[x]=y;up(x);
    printf("%d\n",max(s[x].num[0][0],s[x].num[1][0]));
    }
    return 0;
}

P4751 动态DP加强版

题意:

与上题题意相同

题解:

出题人十分毒瘤

上一题的做法会被卡常 虽然都是一个$logn$的做法 但是LCT的常数过于巨大

我们考虑用全局平衡二叉树(链分治)

我们用树链剖分的思想 取出每条重链

对于每条重链分治找带权重心(每个点的权值是轻儿子的个数加1)构造$BST$

这样形成的树形结构 对于每个点 不管是跳轻边还是重边 都只会是$logn$次

然后用矩阵来维护DP即可

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=1e6+10;
const double eps=1e-8;
const int inf=1e9+9;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
namespace superRead
{
#define BUF_SIZE 5000010
    char buf[BUF_SIZE]; int cur = BUF_SIZE; FILE *in = stdin;
    inline char gnc() {
        if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; }
        return buf[cur++];
    }
    template <typename T> inline void read(T &x) {
        int f = 0; char c = gnc(); x = 0;
        while (!isdigit(c)) f |= c == '-', c = gnc();
        while (isdigit(c)) x = x * 10 + c - 48, c = gnc();
        if (f) x = -x;
    }
    template <typename T, typename... Args>
    inline void read(T& t, Args&... args) {
        read(t); read(args...);
    }
#undef BUF_SIZE
}
using superRead::read;
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
template <typename T> void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }

typedef struct Matrix{
    int num[2][2];
    void init(int x){
    num[0][0]=num[0][1]=0;
    num[1][0]=x;num[1][1]=-inf;
    }
    Matrix operator*(const Matrix &v){
    Matrix ans;
    inc(i,0,1)inc(j,0,1)ans.num[i][j]=-inf;
    ans.num[0][0]=max(num[0][0]+v.num[0][0],num[0][1]+v.num[1][0]);
    ans.num[0][1]=max(num[0][0]+v.num[0][1],num[0][1]+v.num[1][1]);
    ans.num[1][0]=max(num[1][0]+v.num[0][0],num[1][1]+v.num[1][0]);
    ans.num[1][1]=max(num[1][0]+v.num[0][1],num[1][1]+v.num[1][1]);
    return ans;
    }
}Matrix;
Matrix s[MAXN],p[MAXN];
int f[MAXN],son[MAXN],num[MAXN];
void dfs(int x,int pre){
    f[x]=pre;num[x]=1;
    link(x){
    if(j->t==pre)continue;
    dfs(j->t,x);
    num[x]+=num[j->t];
    if(son[x]==-1||num[son[x]]<num[j->t])son[x]=j->t;
    }
}
int tp[MAXN],ch[MAXN][2];
void _dfs(int x,int td){
    tp[x]=td;
    if(son[x]!=-1)_dfs(son[x],td);
    link(x)if(j->t!=son[x]&&j->t!=f[x])_dfs(j->t,j->t);
}
void up(int x){
    s[x]=p[x];
    if(ch[x][0])s[x]=s[ch[x][0]]*s[x];
    if(ch[x][1])s[x]=s[x]*s[ch[x][1]];
}
void __dfs(int x){
    link(x){
    if(j->t==f[x])continue;
    __dfs(j->t);
    if(j->t!=son[x]){
        p[x].num[0][0]+=max(s[j->t].num[0][0],s[j->t].num[1][0]);
        p[x].num[0][1]+=max(s[j->t].num[0][0],s[j->t].num[1][0]);
        p[x].num[1][0]+=s[j->t].num[0][0];
    }
    }
    s[x]=p[x];
    if(son[x]!=-1)s[x]=s[x]*s[son[x]];
}
int st[MAXN],tot,size[MAXN];
int fa[MAXN],a[MAXN];
int fbuilt(int l,int r){
    if(l>r)return 0;
    ll sum1=0,sum2=0;
    inc(i,l,r)sum1+=size[i];
    inc(i,l,r){
    if(2*(sum2+size[i])>=sum1){
        int lx=fbuilt(l,i-1);int rx=fbuilt(i+1,r);
        ch[st[i]][0]=lx;ch[st[i]][1]=rx;
        fa[lx]=st[i];fa[rx]=st[i];
        up(st[i]);
        return st[i];
    }
    else sum2+=size[i];
    }
}
bool check(int x,int y){
    if(x==0||y==0)return 1;
    if(tp[x]==tp[y])return 1;
    return 0;
}
int built(int x){
    tot=0;
    while(x!=-1){
    st[++tot]=x;
    if(son[x]!=-1)size[tot]=num[x]-num[son[x]];
    else size[x]=1;
    x=son[x];
    }
    return fbuilt(1,tot);
}

void update(int x,int y){
    p[x].num[1][0]+=(y-a[x]);a[x]=y;
    while(x){
    if(fa[x]&&!check(x,fa[x])){
          p[fa[x]].num[1][0]-=s[x].num[0][0];
          p[fa[x]].num[0][0]-=max(s[x].num[0][0],s[x].num[1][0]);
          p[fa[x]].num[0][1]-=max(s[x].num[0][0],s[x].num[1][0]);
          up(x);
          p[fa[x]].num[1][0]+=s[x].num[0][0];
          p[fa[x]].num[0][0]+=max(s[x].num[0][0],s[x].num[1][0]);
          p[fa[x]].num[0][1]+=max(s[x].num[0][0],s[x].num[1][0]);
    }
    else up(x);
    x=fa[x];
    }
}
int n,m;
int main(){
    read(n,m);
    inc(i,1,n)read(a[i]),p[i].init(a[i]),s[i].init(-inf),son[i]=-1;
    int x,y;
    inc(i,2,n)read(x,y),add(x,y),add(y,x);
    dfs(1,0);_dfs(1,1);__dfs(1);
    inc(i,1,n)if(tp[i]==i)fa[built(i)]=f[i];
    int rt;
    inc(i,1,n)if(!fa[i])rt=i;
    int Ans=0;
    while(m--){
    read(x,y);x^=Ans;
    update(x,y);
    Ans=max(s[rt].num[0][0],s[rt].num[1][0]);
    writeln(Ans);
    }
    return 0;
}