帮我解释这个转移:
小号悬赏一个关注
教练看着我写的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,0 表示当前节点(i)被它的儿子看管且以 i 为根节点的子树内所有点均被看管的最小花费;
fi,1 表示当前节点(i)被自己看管且以 i 为根节点的子树内所有点均被看管的最小花费;
fi,2 表示当前节点(i)被父亲节点看管且以 i 为根节点的子树内所有点均被看管的最小花费。
好吧写的有点复杂
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 ;
}
哪位大佬解释一下状态转移方程,上课没听明白.