UVALive 4685 Succession 树DP+背包

一、前言

　　这道题同样来自于红书P142，作为树DP专题中的一道比较难的题目，A了一天左右的时间，看上去事实证明，这题的难度理我本身的实力还是有些太远了，于是正确的做法应该是分析一下题目之后进行解析什么的之后上VJ找AC代码，然后结合对状态转移方程的理解补出题解中没有提到或者。。搞错了的部分。于是看上去只有这种方法能够比较高效的进行自我扫盲什么的。作为一只萌新，成功的在刷这本书的过程中体验到了所谓“菜是原罪”这种奇妙的含义。

二、题意

　　原题很长，但是大概的意思是，N各节点的一棵树，要求你找出，K大小的联通块中的权值最大值，以及所有能够构成最大值的K大联通块的构成方案数。

三、思路和坑

　　这道题作为卡了我好久的一道题，看上去思路和前面一篇苹果树的题目有些奇妙的异曲同工之处——都是一个套路甚至代码可以互相改了用

　　大概的思路是设置两个状态转移方程进行同步转移：

　1、DP【】【】用来保存“某节点，权值最大的，大小为J的联通块的组成数量”

　2、SUMM【】【】用来保存某节点权值最大的，大小为J的联通块的权值

　　于是，我们可以子啊转移SUMM【】【】的时候把DP【】【】作为一个附属属性进行转移：当相同的时候进行加和，但是当有最大值出现的时候直接复制最大值的解决方案。

对于如何进行枚举实际上很容易想到的是0-1背包：
对于每个大小的子节点视为物品：权重是ARR[TAR]，重量是尺寸。
之后认为背包容量就是总容量：SHARE，也就是前文提到的k。然后使用0-1背包特有的从上到下的方式进行状态转移。每个DFS中看上去有三重循环但是实际上由于每个节点只会被调用一次所以实际上时间复杂度是O(N*SHARE)。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define veci vector<int>

#define stai stack<int>

const long long MAXN=;

const long long INF=<<;

const long long MOD=1e9+;

veci G[MAXN];

ll arr[MAXN],dp[MAXN][MAXN],summ[MAXN][MAXN];

ll n,SHARE,ans,maxx,r;

void dfs(int now,int last)

{

    int len=G[now].size();

    dp[now][]=;

    summ[now][]=arr[now];

    summ[now][]=;

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

    {

        int tar=G[now][i];

        if(tar==last)continue;

        dfs(tar,now);

//使用0-1背包进行状态转移

        for(int j=SHARE;j;j--)

        {

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

            {

                ll newSum=summ[now][j]+summ[tar][k];

                if(summ[now][j+k]==newSum)

                {

                    dp[now][j+k]+=(dp[now][j]*dp[tar][k])%MOD;

                    dp[now][j+k]%=MOD;

                }

                if(summ[now][j+k]<newSum)

                {

                    summ[now][j+k]=newSum;

                    dp[now][j+k]=(dp[now][j]*dp[tar][k])%MOD;

                }

            }

        }

    }

    if(maxx<summ[now][SHARE])

    {

        maxx=summ[now][SHARE];

        ans=dp[now][SHARE];

    }else if(maxx==summ[now][SHARE])

    {

        ans+=dp[now][SHARE];

        ans%=MOD;

    }

}

void init()

{

    cin>>n>>SHARE>>r;

    ans=;maxx=-INF;

    r=n-;

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

    {

        G[i].clear();

        cin>>arr[i];

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

        {

            dp[i][j]=;

            summ[i][j]=-INF;

        }

    }

    while(r--)

    {

        int a,b;

        cin>>a>>b;

        G[a].push_back(b);

        G[b].push_back(a);

    }dfs(,-);

    cout<<maxx<<" "<<ans<<"\n";

}

int main()

{

    cin.sync_with_stdio(false);

    int ca;cin>>ca;

    while(ca--)init();

    return ;

}

巴特西

UVALive 4685 Succession 树DP+背包

一、前言

二、题意

三、思路和坑

最新文章

热门文章