说句闲话:研究树形DP的最好方法是
查看原帖
说句闲话:研究树形DP的最好方法是
1015780
newbieTroll楼主2024/1/2 12:47

帮我解释这个转移:

小号悬赏一个关注

教练看着我写的AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mzgwty teacher
const int N=1505;
int n;
int w[N],f[N][3];
vector<int> G[N];
void dfs(int u,int fa){
	f[u][1]=w[u];
	int minn=INT_MAX;
	for(auto v:G[u]) if(v!=fa){
		dfs(v,u);
		f[u][2]+=min(f[v][0],f[v][1]);
		f[u][1]+=min({f[v][0],f[v][1],f[v][2]});
		f[u][0]+=min(f[v][0],f[v][1]);
		minn=min(minn,f[v][1]-min(f[v][0],f[v][1]));
	}f[u][0]+=minn;
	return ;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	int fuck,k,m,x;
	for(int i=1;i<=n;++i){
		cin>>fuck>>k>>m;
		w[fuck]=k;
		while(m--){
			cin>>x;
			G[x].push_back(fuck);
			G[fuck].push_back(x);
		}
	}dfs(1,0);
	cout<<min(f[1][0],f[1][1])<<endl;
    return 0;
}

仔细看这段代码你会知道我教练的luogu用户名

他给我讲的 dp 数组表示:

fi,0f_{i,0} 表示当前节点(ii)被它的儿子看管且以 ii 为根节点的子树内所有点均被看管的最小花费;

fi,1f_{i,1} 表示当前节点(ii)被自己看管且以 ii 为根节点的子树内所有点均被看管的最小花费;

fi,2f_{i,2} 表示当前节点(ii)被父亲节点看管且以 ii 为根节点的子树内所有点均被看管的最小花费。

好吧写的有点复杂

dfs 部分:

void dfs(int u,int fa){
	f[u][1]=w[u];
	int minn=INT_MAX;
	for(auto v:G[u]) if(v!=fa){
		dfs(v,u);
		f[u][2]+=min(f[v][0],f[v][1]);
		f[u][1]+=min({f[v][0],f[v][1],f[v][2]});
		f[u][0]+=min(f[v][0],f[v][1]);
		minn=min(minn,f[v][1]-min(f[v][0],f[v][1]));
	}f[u][0]+=minn;
	return ;
}

哪位大佬解释一下状态转移方程,上课没听明白.

2024/1/2 12:47
加载中...