本题解是在官方题解基础上写些自己的理解。题意略
大致思路:对于每个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) 回帖