竞赛讨论区 > 多校训练营(第二场)B 基环树dp
头像
CToshi
编辑于 2018-07-23 11:01
+ 关注

多校训练营(第二场)B 基环树dp

本题解是在官方题解基础上写些自己的理解。题意略
大致思路:对于每个i和f[i],将其视为一条边f[i] -> i,则有n个点n条边,是多个基环树(一棵树加任意一条边则形成基环树),思路是断环为链
子问题:考虑少一条边时,即树的情况怎么做。
本来n条边时,每个点都有入边,少一条边后,设没有入边的点为root,即少了 f[root] -> root边。此问题用树dp即可
状态定义:设dp[u][way]表示u点及其孩子的总的最小费用,且u点必须使用way的方式购买,way为0,1,2分别表示,免费、第一种优惠和第二种优惠
如何转移:way为1或2时,u与其孩子无关,则每个孩子取三种方式中的最小费用即可
way为0时,u必须由某个孩子使用第二种优惠购买,而其它的孩子可以取任意方式的最小
回到本题:先去掉环上任意一边edge,设edge = node -> root,由子问题我们知道此时可以确定一个根,接下来有两种情况:
1、根不使用第二种优惠,此时edge有无一样,由子问题解决
2、根使用第二种优惠,此时node只能使用way=0的方式、即免费获得
那么,此时状态定义要多一维,即第一种情况和第二种情况,详见代码
另外找要删除的边,即环上一边时,可以用并查集
核心代码:
ll dp[N][3][2];
vector<int> G[N]; // 存单向边
vector<ll> chans[N]; // 记录孩子答案
ll dfs(int u,int mustfree, int way){
    ll &ret = dp[u][way][mustfree!=0]; //第一种情况时mustfree传入0
    if(ret!=-1) return ret; // 记忆化
    if(u==mustfree && way) return ret = INF; //mustfree结点只能免费获得
    int cost = 0;
    if (way==1) cost = p[u] - d[u];
    else if(way==2)cost = p[u]; //cost=u点费用
    bool isleaf = true;
    ll sum = 0;
    for(int i = 0;i<(int)G[u].size();i++){
        int v = G[u][i];
        isleaf = false;
        ll& t = chans[u][i];
        t = INF;
        rep(k,3) {
            t = min(t, dfs(v, mustfree, k));
        }
        sum += t;
    }
    if(u != mustfree && isleaf && !way) return ret = INF;
    //u!=mustfree时,要免费获得u那u必须有孩子结点
    ret = INF;
    if(!way && u != mustfree){ //免费获得u时,必须有一个孩子使用第二种优惠
        for(int i = 0;i<(int)G[u].size();i++){
            int v = G[u][i];
            ret = min(ret, sum - chans[u][i] + dp[v][2][mustfree!=0] + cost);
        }
    } else ret = sum + cost;
    return ret;
}


全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐