DP训练——树形DP

2020-02-23 本文已影响0人云中翻月

树形DP

BZOJ4472
题意
$n(n<=100000)$ 个点的无根树， $1$ 号点为根节点。除1号点外，其他所有点均有访问次数限制和价值。
现求从 $1$ 号点出发，最终回到 $1$ 号点的最大收益，并确定方案是否唯一。
方案唯一，指存在两个收益均为最大收益的方案，经过的城市集合不同(即不考虑城市顺序)。
题解
对于节点 $x$ ，它能够遍历的子树个数为 $cnt[x]-1$ 。
因此， $x$ 的最优解一定来自于其收益和最大的 $cnt[x]-1$ 棵子树。
同时，如果这 $cnt[x]-1$ 颗子树中存在收益和为 $0$ 的子树（可以选也可以不选），那么方案不唯一。
如果第 $cnt[x]-1$ 和第 $cnt[x]$ 的子树收益相等（可以交换），那么方案也不唯一。
如此一来，统计完了子树后，向着父节点转移即可。
具体地说，我们分别考虑最优解的计算和是否存在唯一方案的计算。
状态定义： $f[i]$ 表示以 $i$ 为根的子树的最大收益
目标： $f[1]$
边界： $f[i]=val[i]$
转移方程： $f[i]=\sum_{j_k为i的子节点，且为i的子结点中最大的前cnt[i]-1个f[j_k]}f[j_k],f[j_k]>0$
状态定义： $flag[i]$ 表示获得以 $i$ 为根的子树的最大收益的方案数是否唯一( $flag[i]=0$ 表示唯一)
目标： $flag[1]$
边界： $flag[i]=0$
转移方程： $flag[i]=flag[j_k] \;\;OR\;\; f[j_k]==0\;\; OR\;\; f[a[cnt[i]-1]]==f[a[cnt[i]]],f[j_k]>0$
$j_k$ 为 $i$ 的子节点，且为 $i$ 的子结点中最大的前 $cnt[i]-1$ 个 $f[j_k]$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int maxm=maxn-1;
const int INF=0x3f3f3f3f;
int n;
int head[maxn],tot=1;
int cnt[maxn]; //每个点的停留次数上限
int val[maxn];
int f[maxn],flag[maxn];
struct node{
    int from,to;
}edge[maxm<<1];
void add(int from,int to){
    edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
int a[maxn],pos;
bool cmp(const int &i,const int &j){
    return f[i]>f[j];
}
void dfs(int x,int fa){
    f[x]=val[x];
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==fa) continue;
        dfs(y,x);
    }
    pos=0;
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==fa) continue;
        a[++pos]=y;
    }
    sort(a+1,a+pos+1,cmp);
    for(int i=1;i<=pos;i++){
        if(i>cnt[x]-1) break;
        if(f[a[i]]>0) f[x]+=f[a[i]];
        if(f[a[i]]==0) flag[a[i]]=1;
        if(i==cnt[x]-1&&f[a[i]]>0&&i+1<=pos&&f[a[i]]==f[a[i+1]]) flag[a[i]]=1;
        flag[x]|=flag[a[i]];
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ4472.in","r",stdin);
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",&val[i]);
    for(int i=2;i<=n;i++) scanf("%d",&cnt[i]);
    cnt[1]=INF;
    int from,to;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&from,&to);
        add(from,to),add(to,from);
    }
    dfs(1,-1);
    printf("%d\n",f[1]);
    if(flag[1]) printf("solution is not unique");
    else printf("solution is unique");
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ1864
题意
给定一颗 $n(n<=500000)$ 个点的二叉树，节点有三种颜色。颜色规律满足父子节点和兄弟节点颜色不同，求绿色节点数的最小值和最大值。
题解
根据字符串递归建树，然后dp即可。(代码中在建树时采用了引用简化的方式)
状态定义： $f[i,j](j=0,1,2)$ 表示 $i$ 号点所在子树中， $i$ 染成绿色/红色/蓝色的情况下，绿色点的最大数量。
目标： $max{f[rt,0],f[rt,1],f[rt,2]}$
边界： $f[i,0]=1$
转移方程：
$f[x,0]=max(f[l,1]+f[r,2],f[l,2]+f[r,1])+1$
$f[x,1]=max(f[l,0]+f[r,2],f[l,2]+f[r,0])$
$f[x,2]=max(f[l,0]+f[r,1],f[l,1]+f[r,0])$
状态定义： $d[i,j](j=0,1,2)$ 表示 $i$ 号点所在子树中， $i$ 染成绿色/红色/蓝色的情况下，绿色点的最小数量。
目标： $min{d[rt,0],d[rt,1],d[rt,2]}$
边界： $d[i,0]=1$
转移方程：
$d[x,0]=min(d[l,1]+d[r,2],d[l,2]+d[r,1])+1$
$d[x,1]=min(d[l,0]+d[r,2],d[l,2]+d[r,0])$
$d[x,2]=min(d[l,0]+d[r,1],d[l,1]+d[r,0])$
每个点有三种状态，因此时间复杂度为 $O(n)$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=500000+5;
const int maxm=maxn-1;
const int INF=0x3f3f3f3f;
int n;
char s[maxn];
int son[maxn][2]; //son[i,0]表示i的左儿子编号 son[i,1]表示i的右儿子编号
int cnt=0;
int rt;
int f[maxn][3];//f[i,j](j=0,1,2)表示i号点所在子树中，i染成绿色/红色/蓝色的情况下，绿色点的最大数量
int d[maxn][3];//d[i,j](j=0,1,2)表示i号点所在子树中，i染成绿色/红色/蓝色的情况下，绿色点的最小数量
void build(int &x){
    x=++cnt;
    if(s[x]=='1') build(son[x][0]);
    if(s[x]=='2'){
        build(son[x][0]);
        build(son[x][1]);
    }
}
void dp1(int x){
    if(x==0) return;
    int l=son[x][0],r=son[x][1];
    dp1(l),dp1(r);
    f[x][0]=max(f[l][1]+f[r][2],f[l][2]+f[r][1])+1;
    f[x][1]=max(f[l][0]+f[r][2],f[l][2]+f[r][0]);
    f[x][2]=max(f[l][0]+f[r][1],f[l][1]+f[r][0]);
}
void dp2(int x){
    if(x==0) return;
    int l=son[x][0],r=son[x][1];
    dp2(l),dp2(r);
    d[x][0]=min(d[l][1]+d[r][2],d[l][2]+d[r][1])+1;
    d[x][1]=min(d[l][0]+d[r][2],d[l][2]+d[r][0]);
    d[x][2]=min(d[l][0]+d[r][1],d[l][1]+d[r][0]);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ1864.in","r",stdin);
    scanf("%s",s+1);
    n=strlen(s);
    build(rt);
    dp1(rt);
    dp2(rt);
    int ans1=max(f[rt][0],max(f[rt][1],f[rt][2]));
    int ans2=min(d[rt][0],max(d[rt][1],d[rt][2]));
    printf("%d\n%d",ans1,ans2);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ4033
题意
一棵点数为 $n(n<=2000)$ 的树，树边有边权。要在这棵树中选择 $K$ 个点，将其染成黑色，并将其他点染成白色。
将所有点染色后，收益为黑点两两之间的距离加上白点两两之间距离的和。求收益最大值。
题解
因为贡献的特征，因此对于 $x$ 的子节点 $y$ ，产生贡献的时候，要去考虑 $x$ 中的黑点个数和 $y$ 中的黑点个数。
状态定义： $f[i,j]$ 表示从以 $i$ 为根的子树中，选择 $j$ 个点染成黑色对答案的贡献
目标： $f[i,0]=f[i,1]=0$
边界： $f[1,k]$
转移方程： $f[x,j]=max(f[x,j-l]+f[y,l]+val)$ ( $y$ 为 $x$ 子节点)
$val=v*(l*(k-l)+(sz[y]-l)*(n-sz[y]-(k-l)))$
其中， $v$ 为 $<x,y>$ 的权值。
$l$ 为 $y$ 节点所在集合选出的黑点数(该集合可理解为包含 $y$ 但不包含 $x$ 的极大连通图)， $k-l$ 为 $x$ 节点所在集合选出的黑点数。
$sz[y]-l$ 为y节点所在集合选出的白点数， $n-sz[y]-(k-l)$ 为 $x$ 节点所在集合选出的白点数。
即 $val$ 为枚举 $x$ 节点所在集合的黑点数和y节点所在集合的黑点数后，边 $<x,y>$ 产生的贡献。
PS：转移顺序问题
我们在第一层的转移中，为了保证不重复转移（跟01背包压掉一维后的倒序转移一样），我们倒序转移。
在第二层的转移顺序的问题上，我认为：
1.正序转移和倒序转移在本质上并没有差别，但是在这道题中，对于当前枚举的子节点的子树，
哪怕一个黑点也没有，它仍然可以对答案产生贡献，所以我们要先算上这种情况的贡献，
否则在接下来的转移中，就会少计算本来就有的价值，从而答案错误。
2.正序枚举的好处在于，它会先枚举在当前枚举的子节点的子树中一个黑点也没有的情况，
从而直接加上这种情况的贡献，转移就变得比较方便。
3.第二层正序枚举为什么不会重复转移的问题在这里也说一下，
我们发现，我们第二层的枚举一直是在转移同一个状态(即代码中的 $f[x][j]$ )，
所以正序并不会用被当前枚举的子节点更新过的信息，所以并不会重复转移。
题解链接 https://blog.csdn.net/Diogenes_/article/details/81044483
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int INF=0x3f3f3f3f;
ll f[maxn][maxn];//f[i,j]表示从以i为根的子树中 选择j个点染成黑色对答案的贡献
struct node{
    int from,to;
    ll v;
}edge[maxn<<1];
int n,k;
int head[maxn],tot=1;
void add(int from,int to,ll v){
    edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].v=v;
}
int sz[maxn];
void dfs(int x,int fa){
    memset(f[x],-1,sizeof(f[x]));
    f[x][0]=f[x][1]=0;
    sz[x]=1;
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==fa) continue;
        dfs(y,x);
        sz[x]+=sz[y];
    }
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==fa) continue;
        ll v=edge[i].v;
        for(int j=min(sz[x],k);j>=0;j--){
            for(int l=0;l<=min(j,sz[y]);l++){
                if(f[x][j-l]==-1) continue; 
                ll val=v*(l*(k-l)+(sz[y]-l)*(n-sz[y]-(k-l)));
 //               D(val);E;
                f[x][j]=max(f[x][j],f[x][j-l]+f[y][l]+val);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ4033.in","r",stdin);
    cin>>n>>k;
    int from,to;
    ll v;
    for(int i=1;i<=n-1;i++){
        cin>>from>>to>>v;
        add(from,to,v),add(to,from,v);
    }
    dfs(1,0);
    cout<<f[1][k];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ4446
题意
$n(n<=2e5)$ 个点的完全二叉树，存在点权和边权，点亮第一个点无代价。（这个点不一定是根节点）
之后每点亮一个点的代价，等于上一个被点亮的点到这个点的距离，乘以这个点的权值。
在点亮的过程中，要保证任意时刻所有被点亮的点必须连通，在点亮一个点后必须先点亮其子树所有点才能点亮其他点。
求点亮所有点的最小代价。
题解
由于是一棵完全二叉树，所以深度最大只有 $logn$ ，所以可以引入深度作为状态。
其次注意到记录上一个点亮的点较为困难，但能计算下一个点亮的点。
具体地说，即点完以 $i$ 点为根的子树之后，下一个只能点量 $i$ 的某个祖先，或者 $i$ 的某个祖先的兄弟。
因此，基于如上两点，可进行下面的dp。
状态定义：
$f[i,j,0]$ 表示点完以第 $i$ 个点为根节点的子树之后，再去点其第 $j$ 个祖先的过程需要的最小花费
$f[i,j,1]$ 表示点完以第 $i$ 个点为根节点的子树之后，再去点其第 $j+1$ 个祖先的另一个儿子（与第 $j$ 个祖先不同的儿子）的过程需要的最小花费
目标：所有 $f$ 数组，用于后续计算
边界： $f[i,j,0]=f[i,j,1]=INF$
转移方程：根据 $i$ 节点的子节点数分为三类讨论，具体详见代码。
关于使用dp数组拼凑答案。
注意到确定第一个点亮的点后，可以根据dp数组确定点亮的顺序。因此枚举第一个点亮的点，然后当前点亮的节点是否存在兄弟节点计算结果即可。
PS：由于完全二叉树间存在节点编号关系，所以可以从 $n$ 到 $1$ 逆序递推dp数组。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int maxlogn=20;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n;
ll num[maxn];
ll dis[maxn][maxlogn]; //dis[i,j]表示i到i的j级祖先的距离
ll f[maxn][maxlogn][2];
ll ans=INF;
int p(int i,int j){ //返回i的j级祖先编号 1级祖先就是i的父亲 并且上设0号虚拟节点作为根节点 num[0]=0 dis[1][1]=0
    if((1<<j-1)<=i) return (i>>j);
    return -1; //-1表示i不存在j+1级祖先
}
int b(int i,int j){ //返回i的j级祖先的另一个儿子编号
    return ((i>>j-1)^1);
}
int l(int i){ //返回i的左儿子编号
    return (i<<1);
}
int r(int i){ //返回i的右儿子编号
    return ((i<<1)|1);
}
void dp(){
    for(int i=n;i>=1;i--){ //逆序循环 保证从叶子节点向父节点转移
        for(int j=1;~p(i,j);j++){
            f[i][j][0]=f[i][j][1]=INF;
            if(l(i)>n){ //叶子节点
                f[i][j][0]=num[p(i,j)]*dis[i][j];
                f[i][j][1]=num[b(i,j)]*(dis[i][j]+dis[b(i,j)][1]);
            }
            else if(l(i)==n){ //只有一个左子节点
                f[i][j][0]=f[l(i)][j+1][0]+dis[l(i)][1]*num[l(i)];
                f[i][j][1]=f[l(i)][j+1][1]+dis[l(i)][1]*num[l(i)];
            }
            else{ //有左右子节点
                f[i][j][0]=min(f[i][j][0],f[l(i)][1][1]+f[r(i)][j+1][0]+dis[l(i)][1]*num[l(i)]);
                f[i][j][0]=min(f[i][j][0],f[r(i)][1][1]+f[l(i)][j+1][0]+dis[r(i)][1]*num[r(i)]);
                f[i][j][1]=min(f[i][j][1],f[l(i)][1][1]+f[r(i)][j+1][1]+dis[l(i)][1]*num[l(i)]);
                f[i][j][1]=min(f[i][j][1],f[r(i)][1][1]+f[l(i)][j+1][1]+dis[r(i)][1]*num[r(i)]);
            }
        }
    }
}
void solve(){
    for(int s=1;s<=n;s++){ //枚举起点s
        ll temp=f[s][1][0]; //点亮s所在的子树
        for(int i=p(s,1),last=s;~i;i=p(i,1),last=p(last,1)){ //last为上一个点亮的子树的根节点
            //last节点的子树和i节点已经被点亮 当前位于i节点 现在要点亮i的父亲节点
            if(b(last,1)<=n){ //i存在兄弟节点 则先点亮兄弟节点 后点亮父节点
                temp+=dis[b(last,1)][1]*num[b(last,1)]+f[b(last,1)][2][0];
            }
            else{ //i没有兄弟节点 那么直接点亮父节点 
                temp+=dis[i][1]*num[p(i,1)];
            }
        }
        ans=min(ans,temp);
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ4446.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for(int i=2;i<=n;i++){
        scanf("%lld",&dis[i][1]);
        for(int j=2;~p(i,j);j++) dis[i][j]=dis[p(i,j-1)][1]+dis[i][j-1];
    }
    dp();
    solve();
    printf("%lld",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

DP训练——树形DP

树形DP

猜你喜欢

热点阅读