dp专题

dp 太弱了。被梁老抓去写题单。花了一天把绿题补完。

老是看出一道题显然 dp 又死活做不出来。

以下除最后一篇外都是绿题难度。

---

P5322 [BJOI2019] 排兵布阵

Problem Link

题目大意

给定 n 个长为 s 的序列 $A_{1,s},A_{2,s},...A_{n,s}$，要求构造一个长为 n 的序列 $P_n$，

满足 $\sum P_i\le m$，且 $\sum [P_i>2\times A_{i,u}]\times i$ 最大。

思路分析

把 $m$ 和 $n$ 两维摘出来，设 $f_{i,j}$ 表示前 $i$ 座城堡投入 $j$ 的兵力所得的最大得分。

观察特征，对于一个城堡的投入，只有 $2\times A_{i,u}+1$​ 是有效的。因此可以转化成背包问题。

处理一下费用 $w$ 和价值 $v$ 的转化：将 $A_i$ 排序，此时对于每个 $A_i$ 可以计算出投入对应兵力的费用 $2\times A_{i,u}+1$ 和价值 $u\times i$。

对于这个背包模型，具体地，共有 $n$ 组物品，每组最多选一个，求总容量为 $m$ 时最大价值。这是一个经典的分组背包问题（尽管我才知道它叫什么），相当于每组物品分别跑背包，再进行合并。

状态转移表示：$f_{i,j}=\max (f_{i,j},f_{i,k-w_t}+v_t)$​​。复杂度 $O(nms)$。

看到模型，拨开云雾见月明。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int s,n,m,a[105][105],f[20005];
int main(){
    scanf("%d%d%d",&s,&n,&m);
    rep(j,1,s) rep(i,1,n) scanf("%d",&a[i][j]);
    rep(i,1,n) sort(a[i]+1,a[i]+s+1);
    rep(i,1,n) dec(j,m,0) rep(k,1,s) if(j>=a[i][k]*2+1) f[j]=max(f[j],f[j-a[i][k]*2-1]+i*k);
    printf("%d",f[m]);
}

分组背包的概型：

for(int i=1;i<=n(物品组数);i++)
    for(int j=m(当前组背包容量);j>=0;j--)
        for(int k=1;k<=s(枚举当前组物品);k++)

树上背包更经典，均摊复杂度 $O(n|W|)$ 很精妙，下文的P1273会讲。

---

P2458 [SDOI2006] 保安站岗

Problem Link

题目大意

给定一棵树，每个点点权为 $r_i$，定义一个点覆盖范围是周围距离不超过1的点，要求最小费用覆盖整棵树。

思路分析

很经典的树形dp。

第一个想法是设 $f_{u,0/1}$ 为每个点选自己 $/$​ 选子节点的最小值，敲出来迷之WA。原因是存在当前点和子节点都不选也合法的情况。

所f以即使要换根，也要设被父节点覆盖的状态。

补一个状态，设 $f_{u,0/1/2}$ 表示该点被自己覆盖 $/$ 被子节点覆盖 $/$​ 被父节点覆盖，状态转移为：

$$\{\begin{array}{c}{f}_{u,0}=r_u+\sum \min (f_{v,0},f_{v,1},f_{v,2})\\ \\ f_{u,1}=f_{v,0}+({\sum }_{v^{\prime }!=v}\min (f_{v^{\prime },0},f_{v^{\prime },1},f_{v^{\prime },2}))\\ \\ f_{u,2}=\sum \min (f_{v,0},f_{v,1})\end{array}$$

$Ans=\min (f_{rt,0},f_{rt,1})$.

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[1505],f[1505][3];
vector<int> E[1505];
void dfs(int u,int fa){
    f[u][0]=a[u];
    for(int v:E[u]){
        if(v==fa) continue;
        dfs(v,u);
        f[u][0]+=min({f[v][0],f[v][1],f[v][2]});
        f[u][2]+=min(f[v][0],f[v][1]);
    }
    f[u][1]=0x3f3f3f3f;
    for(int v:E[u]){
        if(v==fa) continue;
        f[u][1]=min(f[u][1],f[u][2]-min(f[v][0],f[v][1])+f[v][0]);
    }
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int id;scanf("%d",&id);
        scanf("%d",a+id);
        int op;scanf("%d",&op);
        while (op--){
            int v;scanf("%d",&v);
            E[id].push_back(v);
            E[v].push_back(id);
        }
    }
    dfs(1,0);
    // for(int i=1;i<=n;i++) printf("%d %d %d\n",f[i][0],f[i][1],f[i][2]);
    printf("%d",min(f[1][0],f[1][1]));
    return 0;
}

---

P3174 [HAOI2009] 毛毛虫

Problem Link

题目大意

题目够清晰，没什么大意。

对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就像一个毛毛虫，点数越多，毛毛虫就越大。求毛毛虫所占最多点数。

思路分析

很经典的每个点求答案。考虑只经过每个点所在子树的最值，就是把该点向下延伸的长度最大值和次大值拼接起来。设 $f_u$ 表示 $u$ 向下延伸的最大长度，$s{z}_u$ 为与 $u$ 相连的儿子数，则有 $f_u=\max f_v+(s{z}_u-1)+1+[u有父节点]$。最大值次大值随便乱求。

细节：

• 根节点没有父亲，特殊处理。
• $s{z}_u=1$ 时没有次大值，计算 $Ans$ 时不要少算。（Hack数据）
• 特判 $n=1$ 的情况 $/$ $ans$ 初值赋为1。（Hack数据）

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=3e5+5;
int n,m,f[N],ans=1;
vector<int> E[N];
void dfs(int u,int fa){
    int v1=0,v2=0,sz=E[u].size()-1;f[u]=1;
    for(int v:E[u]){
        if(v==fa) continue;
        dfs(v,u);
        f[u]=max(f[u],f[v]+sz);
        if(f[v]>f[v1]) v2=v1,v1=v;
        else if(f[v]>f[v2]) v2=v;
    }
    ans=max(ans,f[v1]+f[v2]+sz+!v2);
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,m){
        int a,b;scanf("%d%d",&a,&b);
        E[a].push_back(b);E[b].push_back(a);
    }
    dfs(1,-1);
    // rep(i,1,n) printf("%d ",f[i]);puts("");
    printf("%d",ans);
    return 0;
}

---

P3621 [APIO2007] 风铃

Problem Link

题目大意

题目鬼长。

给一棵二叉树，判断其能否通过若干次交换任意节点的左右子树，使它成为一颗完全二叉树且叶子间深度差不超过1，若能，输出最少交换次数。

思路分析

一开始把深度差不超过1理解成了深度种类不超过2

首先考虑判断非法的情况。可以发现只有两种情况非法，一是深度差超过1，二是某个点左右两个子树都存在两种深度。

方便起见，记小深度和大深度为 $D_0,D_1$。对于一个合法二叉树，一个节点 $u$ 会交换左右子树当且仅当左子树有 $D_1$，右子树有 $D_0$。

时间复杂度 $O(n)$。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+5;
int n,nor,Bz,ans,dep[N],ls[N],rs[N],g[N][2];
set<int> st;
void dfs(int x,int f){
    dep[x]=dep[f]+1;
    if(~ls[x]) dfs(ls[x],x);
    else st.insert(dep[x]+1);
    if(~rs[x]) dfs(rs[x],x); 
    else st.insert(dep[x]+1);
}
void dfs2(int x){
    if(~ls[x]) dfs2(ls[x]),g[x][0]|=g[ls[x]][0],g[x][1]|=g[ls[x]][1];
    if(~rs[x]) dfs2(rs[x]),g[x][0]|=g[rs[x]][0],g[x][1]|=g[rs[x]][1];
    if(!(~ls[x]&&~rs[x])) g[x][!(dep[x]+1==nor)]=1;
    if(g[ls[x]][0]&&g[ls[x]][1]&&g[rs[x]][0]&&g[rs[x]][1]) Bz=-1;
    else{
        if(~ls[x]&&~rs[x]) ans+=g[ls[x]][0]&&g[rs[x]][1];
        else if(~rs[x]) ans+=(dep[x]+1==nor&&g[rs[x]][1]);
        else if(~ls[x]) ans+=(g[ls[x]][0]&&dep[x]+1!=nor);
    }
}
int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d%d",ls+i,rs+i);
    dfs(1,0);
    // rep(i,1,n) printf("%d ",dep[i]);puts("");
    if(st.size()>2||st.size()==2&&(*st.rbegin()-*st.begin())!=1) return puts("-1"),0;
    else if(st.size()==1) return puts("0"),0;
    nor=*st.begin();
    dfs2(1);
    // rep(i,1,n) printf("%d %d\n",g[i][0],g[i][1]);
    printf("%d",Bz?Bz:ans);
}

因为这个题的叶子结点是没有编号的，所以都放在它们的父节点处理，使得代码看起来臭长。

不知道我为什么用 $set$ 来处理深度差非法的问题。

---

P1273 有线电视网

Problem Link

题目大意

给定一棵带边权且根为1的原树($N\le 3000$)，每个叶子结点有点权 $v$，请在点权和大于等于边权和的情况下选出根为1的新树，使得选择的叶子结点数量最多。

思路分析

经典的树上分组背包。

由于叶子结点的数目与 $n$ 同阶，而费用值域更大，因此状态设计上不用费用作维度。

对于每个点，记 $f_{u,i}$ 表示节点 $u$ 下选择 $i$ 个叶子结点时累计价值的最大值，目的是当 $f_{u,i}\ge 0$​ 时合法。

每个节点下有若干个物品，每个物品价值为 $f_{v,k}$，费用为 $u,v$ 边权 $W[u,v]$，题意就转化成了一个裸的分组背包。

这题的树上背包复杂度是 $O(n^2)$ 的，优化在于代码的 $s{z}_u+=s{z}_v$（很常规又很精妙的优化方法），即动态更新背包容量，$n=\sum s{z}_u$。具体的证明有很长一段，用简洁的数学解释就是任意两个物品只会在它们的LCA处合并进一个背包，所以复杂度为 $O(n^2)$。

参考资料：

一种树形背包的时间复杂度证明 - Oxide - 博客园 (cnblogs.com)

树上背包的上下界优化 - ouuan - 博客园 (cnblogs.com)

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
using namespace std;
const int N=3e3+5;
int n,m,v[N],f[N][N],sz[N];
vector<pair<int,int> > E[N];
void dfs(int u,int fa){
    f[u][0]=0;
    for(auto V:E[u]){
        int v=V.first,w=V.second;
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        dec(i,sz[u],0) rep(j,1,min(i,sz[v])) f[u][i]=max(f[u][i],f[u][i-j]+f[v][j]-w);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n-m){
        int k;scanf("%d",&k);
        while (k--){int a,c;scanf("%d%d",&a,&c);E[i].push_back({a,c});E[a].push_back({i,c});}
    }
    memset(f,128,sizeof(f));
    rep(i,n-m+1,n) scanf("%d",&f[i][1]),sz[i]=1;
    dfs(1,0);
    dec(i,m,0) if(f[1][i]>=0) return printf("%d",i),0;
}

---

南的彩蛋。Div1 T1

做爽了。

P9180 [COCI2022-2023#5] Slastičarnica

Problem Link

题目大意

复制。

有一列数 $a_1,\dots ,a_n$ $(N\le 5000)$ 和 $q\le 2\cdot 10^5$ 次操作，每次操作形如「删掉长为 $d_i$ 的前缀或后缀，且需要保证这个前缀和后缀中所有元素都大于等于 $s_i$。」每次操作前，你可以选择一个长度任意的前缀或后缀（可以为空），并删除它。如果某次操作无法进行，则停止这次和之后的所有操作。问最多可以进行多少次操作。

思路分析

一眼区间dp。设 $f_{l,r}$ 表示区间 $[l,r]$ 最多进行几次操作。可以选择一个长度任意的前缀或后缀（可以为空），并删除它指明区间 $[l,r]$ 的 $f$ 必然不超过任意一个子区间的 $f$（性质1）。所以基本地，有 $f_{l,r}\to f_{l+1,r},f_{l,r}\to f_{l,r-1}$。

考虑一次操作如何转移，由于 $f_{l,r}=\max (f_{l-1,r},f_{l,r+1})$， $f_{l,r}$ 最多加一。此时的操作编号 $p$ 为 $f_{l,r}+1$。转移 $[l^{\prime },r^{\prime }]\to [l,r]$ 必须满足 $({\min }_{k=l-d_p}^{l-1}{a}_k)\ge s_p$ 的限制，可以用 st 表维护。在满足限制的情况下 $f_{l,r}={\max }_{l^{\prime }=1}^{l-d_p}(f_{l^{\prime },r})$，根据性质1，可以把 $\max$ 丢掉， $f_{l,r}=f_{l-d_p,r}+1$。

细节：注意一定要在前 $i$ 个操作都进行完才能进行下一个操作，所以初始时令 $f_{l,r}=-1,f_{1,n}=0$，只有合法的位置才能进行转移。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=5e3+5,Q=2e5+5;
int n,q,ans,a[N],d[Q],s[Q],st[N][15],f[N][N];
int find(int l,int r){
    int k=log2(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
    // freopen("presuf.in","r",stdin);
    // freopen("presuf.out","w",stdout);
    scanf("%d%d",&n,&q);
    rep(i,1,n) scanf("%d",a+i),st[i][0]=a[i];
    rep(i,1,q) scanf("%d%d",d+i,s+i);
    rep(j,1,14) for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    memset(f,-1,sizeof(f));f[1][n]=0;
    dec(len,n,1){
        rep(l,1,n+1-len){
            int r=l+len-1;
            if(f[l][r]==-1) continue;
            f[l+1][r]=max(f[l+1][r],f[l][r]);
            f[l][r-1]=max(f[l][r-1],f[l][r]);
            int nw=f[l][r]+1;
            if(nw>q) continue;
            if(find(l,l+d[nw]-1)>=s[nw]) f[l+d[nw]][r]=max(f[l+d[nw]][r],f[l][r]+1);
            if(find(r-d[nw]+1,r)>=s[nw]) f[l][r-d[nw]]=max(f[l][r-d[nw]],f[l][r]+1);
        }
    }
    rep(i,1,n) ans=max(ans,f[i][i-1]);
    printf("%d",ans);
}