YBT 5.2 树形动态规划

时间：2022-07-22 23:20:26

题解在代码中

二叉苹果树[loj 10153]

/*

若要留q条边便是要留q+1个点

所以记忆化搜索

dp[pos][ans]=max(dp[pos][ans],dp[l[pos]][k]+dp[r[pos]][ans-k-1]+a[pos])

0<=k<=ans-1

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

int n,q;

int book[][],a[],l[],r[];

void dfs(int pos){

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

    {

        if(book[pos][i]!=-)

        {

            a[i]=book[pos][i];

            book[pos][i]=-;book[i][pos]=-;

            l[pos]=i;

            dfs(i);

            break;

        }

    }

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

    {

        if(book[pos][i]!=-)

        {

            a[i]=book[pos][i];

            book[pos][i]=-;book[i][pos]=-;

            r[pos]=i;

            dfs(i);

            break;

        }

    }

    return;

}

int dp[][];

int solve(int pos,int ans)

{

    if(ans==) return ;

    if(dp[pos][ans]!=-) return dp[pos][ans];

    if(r[pos]==&&l[pos]==) return a[pos];

    for(int j=;j<=ans-;j++)

        dp[pos][ans]=max(dp[pos][ans],solve(l[pos],j)+solve(r[pos],ans--j)+a[pos]);

    return dp[pos][ans];

}

int main()

{

    memset(dp,-,sizeof(dp));

    memset(book,-,sizeof(book));

    n=read(),q=read();

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

    {

        int u=read(),v=read(),w=read();book[u][v]=w;book[v][u]=w;

    }

    dfs();

    cout<<solve(,q+);

}

选课[loj 10154]

/*

建立一个虚根0使得将森林转化成为树

dp[i][j]表示为以i为根的子树下最多选j门课的最大学分

dfs后先进行背包处理

这是先不考虑先修课

再将有先修课 （pos!=0）时dp的容积为容积-1的最大值加上选修此门课的积分

dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son][k])

j (m~0)

    k(j~0)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

int n,m;

struct node{

    int u,v,nex;

}x[];

int s[];

int t,cnt;

int dp[][],head[];

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

void dfs(int pos)

{

    for(int p=head[pos];p!=-;p=x[p].nex)

    {

        int xx=x[p].v;

        dfs(xx);

        for(int i=m;i>=;i--)

            for(int j=i;j>=;j--) dp[pos][i]=max(dp[pos][i],dp[pos][i-j]+dp[xx][j]);

    }

    if(pos!=)

    {

        for(int i=m;i>=;i--)  dp[pos][i]=dp[pos][i-]+s[pos];

    }

//    for(int i=m;i>=0;i--) cout<<"位置："<<pos<<"  选课："<<i<<"  dp:"<<dp[pos][i]<<endl;

//    system("pause");

    return ;

}

int main()

{

    memset(head,-,sizeof(head));

    n=read(),m=read();

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

    {

        t=read(),s[i]=read();

        add(t,i);

    }

    dfs();

    cout<<dp[][m];

}

数字转换[loj 10155]

/*

先预处理好因数和，再建一棵树

求树的最长链即可

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#pragma GCC optimize(2)

using namespace std;

inline long long read()

{

    long long f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

long long n,cnt;

struct node{

    long long u,v,nex;

}x[];

long long head[];

long long dp1[],dp2[];

void add(long long u,long long v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

long long sum[];

long long maxn,book[];

//dp1表示最长,dp2表次长

void dfs(long long pos)

{

//    cout<<pos<<endl;

    for(long long i=head[pos];i!=-;i=x[i].nex)

    {

        long long p=x[i].v;

        if(book[p]==)

        {

            book[p]=;

            dfs(p);

            if(dp1[p]+>dp1[pos]) dp2[pos]=dp1[pos],dp1[pos]=dp1[p]+;

            else if(dp1[p]+>dp2[pos]) dp2[pos]=dp1[p]+;

            maxn=max(maxn,dp1[pos]+dp2[pos]);

        }

    }

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();

    for(int i=;i<=n/;i++)

    {

        for(int j=i*;j<=n;j+=i)

        {

            sum[j]+=i;

        }

    }

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

        if(sum[i]<i) add(sum[i],i),add(i,sum[i]);

    book[]=;

    dfs();

    cout<<maxn;

}

战略游戏[loj 10156]

/*

0为不选，1为选

pos的子孙为x

dp[pos][0]=sum(dp[x][1])

dp[pos][1]=sum(min(dp[x][0],dp[x][1]));

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

struct node{

    int u,v,nex;

}x[];

int head[],n,cnt,dp[][],book[];

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

void dfs(int pos)

{

//    cout<<pos<<endl;

    dp[pos][]=;

    for(int i=head[pos];i!=-;i=x[i].nex)

    {

        int p=x[i].v;

        if(book[p]==)

        {

            book[p]=;

            dfs(p);

            dp[pos][]+=dp[p][];

            dp[pos][]+=min(dp[p][],dp[p][]);

//            cout<<pos<<" "<<dp[pos][0]<<" "<<dp[pos][1]<<" "<<endl;

        }

    }

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();

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

    {

        int t=read(),k=read();

        for(int j=;j<=k;j++)

        {

            int p=read();

            add(t,p),add(p,t);

        }

    }

    book[]=;

    dfs();

    cout<<min(dp[][],dp[][]);

}

皇宫看守[loj 10157]

/*

dp[pos][0]为pos自己安放

dp[pos][1]为pos被自己的父亲看到

dp[pos][2]为pos被自己的子孙看到

dp[pos][0]+=min(dp[x][0],dp[x][1],dp[x][2])

dp[pos][1]+=min(dp[x][0],dp[x][2])

dp[pos][2]+=min(dp[x][0],dp[x][2])

dp[pos][2]+=k,dp[pos][0]+=s[pos]

k=min(k,dp[pos][0]-min(dp[pos][0],dp[pos][2]));

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

int dp[][];

struct node{

    int u,v,nex;

}x[];

int s[];

int a[],cnt,n;

int head[];

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

int dfs(int pos,int fath)

{

    int k=;

    for(int i=head[pos];i!=-;i=x[i].nex)

    {

        int p=x[i].v;

        if(p==fath) continue;

        dfs(p,pos);

        dp[pos][]+=min(min(dp[p][],dp[p][]),dp[p][]);

        dp[pos][]+=min(dp[p][],dp[p][]);

        dp[pos][]+=min(dp[p][],dp[p][]);

        k=min(k,dp[p][]-min(dp[p][],dp[p][]));

    }

    dp[pos][]+=s[pos];

    dp[pos][]+=k;

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();

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

    {

        int xx=read();

        s[xx]=read();

        int m=read();

        for(int j=;j<=m;j++)

        {

            int p=read();

//            cout<<xx<<" "<<p<<endl;

            add(xx,p);

            add(p,xx);

        }

    }

    dfs(,);

    cout<<min(dp[][],dp[][]);

}

加分二叉树[loj 10158]

/*

中序遍历

左子树——根——右子树

每次枚举根

进行记忆化dfs

将last存放最优根

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

int dp[][],s[],n,last[][];

int dfs(int l,int r)

{

//    cout<<l<<" "<<r<<endl;

    if(l==r) return s[l];

    if(l>r) return ;

    if(dp[l][r]!=-) return dp[l][r];

    for(int i=l;i<=r;i++)

    {

        int p=dfs(l,i-)*dfs(i+,r)+s[i];

        if(p>dp[l][r])

        {

            dp[l][r]=p;

            last[l][r]=i;

        }

    }

    return dp[l][r];

}

void sc(int l,int r)

{

    if(l>r) return;

    if(l==r)

    {

        cout<<l<<" ";

        return;

    }

    cout<<last[l][r]<<" ";

    sc(l,last[l][r]-);

    sc(last[l][r]+,r);

    return;

}

int main()

{

    memset(dp,-,sizeof(dp));

    n=read();

    for(int i=;i<=n;i++) s[i]=read();

    cout<<dfs(,n)<<endl;

//    cout<<

    sc(,n);

}

旅游规划[loj 10159]

/*

此题是找最长链上的所有店

dp1求子树上最长路径

dp2求子树上次长路径

两者相加便可以求出最长路径的长度

dp3记录除子树外的最长路径

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

struct node{

    int u,v,nex;

}x[];

int n,cnt,head[];

int book[],dp3[],maxn,dp1[],dp2[];

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

void dfs(int pos)

{

//    cout<<pos<<endl;

    for(int i=head[pos];i!=-;i=x[i].nex)

    {

        int p=x[i].v;

//        cout<<p<<endl;

        if(book[p]==)

        {

            book[p]=;

            dfs(p);

            if(dp1[p]+>=dp1[pos])

            {

                dp2[pos]=dp1[pos];

                dp1[pos]=dp1[p]+;

            }

            else if(dp1[p]+>=dp2[pos])

                dp2[pos]=dp1[p]+;

            maxn=max(maxn,dp1[pos]+dp2[pos]);

        }

    }

    return;

}

void dfs1(int pos,int fath)

{

    int sum=;

    for(int i=head[pos];i!=-;i=x[i].nex)

        if(x[i].v!=fath&&dp1[pos]==dp1[x[i].v]+) sum++;

    for(int i=head[pos];i!=-;i=x[i].nex)

    {

        if(x[i].v!=fath)

        {

            if(dp1[x[i].v]+!=dp1[pos]) dp3[x[i].v]=max(dp1[pos],dp3[pos])+;

            else if(dp1[x[i].v]+==dp1[pos]&&sum>)dp3[x[i].v]=max(dp1[pos],dp3[pos])+;

            else dp3[x[i].v]=max(dp2[pos],dp3[pos])+;

            dfs1(x[i].v,pos);

        }

    }

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();

//    for(int i=0;i<n;i++) f[i]=i;

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

    {

        int u=read(),v=read();

        add(u,v),add(v,u);

    }

    book[]=;

    dfs();

//    cout<<maxn<<" ";

    memset(book,,sizeof(book));

    dfs1(,-);

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

        if(dp1[i]+max(dp2[i],dp3[i])==maxn) cout<<i<<endl;

    return ;

}

周年纪念晚会[loj 10160]

/*

0不选1选

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

int a[],n;

struct node{

    int u,v,nex;

}x[];

int cnt;

int head[],dp[][],t[];

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

void dfs(int pos)

{

//    cout<<pos<<endl;

    dp[pos][]=;

    dp[pos][]=a[pos];

    for(int i=head[pos];i!=-;i=x[i].nex)

    {

        int p=x[i].v;

        dfs(p);

        dp[pos][]+=max(,max(dp[p][],dp[p][]));

        dp[pos][]+=max(,dp[p][]);

    }

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();

    memset(dp,0xcf,sizeof(dp));

    for(int i=;i<=n;i++) a[i]=read();

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

    {

        int u=read(),v=read();

        add(v,u);t[u]=;

    }

    int sry=;

    while(t[sry]==) sry++;

    dfs(sry);

    cout<<max(dp[sry][],dp[sry][]);

}

叶子的颜色[loj 10161]

/*

dp[pos][0]表示pos涂黑色

1 表示涂白色

2 表示不涂

dp[pos][0]+=min(dp[x][0]-1,dp[x][1],dp[x][2])

1,2同理

-1是因为此点就不需要涂 

预处理见代码

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

int m,n,c[];

struct node{

    int u,v,nex;

}x[];

int head[],cnt;

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

int book[],dp[][];

void dfs(int pos)

{

    if(pos>=&&pos<=m)

    {

        dp[pos][c[pos]]=;

        dp[pos][-c[pos]]=dp[pos][]=<<-;

    }

    else{

        dp[pos][]=dp[pos][]=;

    }

    for(int i=head[pos];i!=-;i=x[i].nex)

    {

        int t=x[i].v;

        if(book[t]==)

        {

            book[t]=;

            dfs(t);

            dp[pos][]+=min(dp[t][]-,min(dp[t][],dp[t][]));

            dp[pos][]+=min(dp[t][]-,min(dp[t][],dp[t][]));

            dp[pos][]+=min(dp[t][],min(dp[t][],dp[t][]));

        }

    }

}

int main()

{

    memset(head,-,sizeof(head));

    n=read(),m=read();

    for(int i=;i<=m;i++) c[i]=read();

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

    {

        int u=read(),v=read();

        add(u,v),add(v,u);

    }

    book[n]=;

    dfs(n);

    cout<<min(dp[n][],min(dp[n][],dp[n][]));

}

骑士[loj 10162]

/*

断环为链,与没有上司的舞会接下来的十分相似

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline long long read()

{

    long long f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

struct node{

    long long u,v,nex;

}x[];

long long cnt;

long long head[],n,s[],vis[],root,book[],uu,vv;

void add(long long u,long long v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

bool flag;

long long ans;

void dfs(long long pos,long long fa)

{

    for(long long i=head[pos];i!=-;i=x[i].nex)

    {

        long long p=x[i].v;

        if(fa!=p)

        {

            if(vis[p]==)

            {

                vis[p]=;

                dfs(p,pos);

            }

            else{

                flag=true;

                uu=pos,vv=p;

            }

        }

    }

}

long long dp[][];//0没用，1用

long long inf=<<-;

void dfs_dp(long long pos,long long fa)

{

//    cout<<pos<<endl;

    dp[pos][]=s[pos];

    for(long long i=head[pos];i!=-;i=x[i].nex)

    {

        long long p=x[i].v;

        if(p!=fa)

        {

            if(p==-inf) continue;

            dfs_dp(p,pos);

            dp[pos][]+=max(dp[p][],dp[p][]);

            dp[pos][]+=dp[p][];

        }

    }

    return;

}

void work(long long pos)

{

    memset(dp,,sizeof(dp));

    flag=false;

    vis[pos]=;

    dfs(pos,-);

//    cout<<uu<<" "<<vv<<endl;

    if(flag==false)

    {

        dfs_dp(pos,-);

        ans+=max(dp[pos][],dp[pos][]);

    }

    else if(flag==true)

    {

        long long maxn=;

        for(long long i=head[uu];i!=-;i=x[i].nex)

        {

            long long p=x[i].v;

            if(p==vv)

            {

                x[i].v=-inf;

                break;

            }

        }

        for(long long i=head[vv];i!=-;i=x[i].nex)

        {

            long long p=x[i].v;

            if(p==uu)

            {

                x[i].v=-inf;

                break;

            }

        }

//        cout<<uu<<" "<<vv<<endl;

        dfs_dp(uu,-);

//        return ;

        long long x1=dp[uu][];

//        cout<<x1<<endl;

        memset(dp,,sizeof(dp));

        dfs_dp(vv,-);

        long long x2=dp[vv][];

//        cout<<x2<<endl;

        maxn=max(x1,x2);

        ans+=maxn;

    }

}

int main(void)

{

    memset(head,-,sizeof(head));

    n=read();

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

    {

        s[i]=read();

        long long p=read();

        add(i,p),add(p,i);

    }

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

    {

        if(vis[i]==)

        {

            work(i);

//            return 0;

        }

    }

    cout<<ans;

}

相关文章