进食后人:如果你只建了一个正向的图
查看原帖
进食后人:如果你只建了一个正向的图
822439
lhz2022楼主2025/1/21 20:50

在dp的时候,你大概率是这样dp的:

for(int i=1;i<=scc;++i){
	int u=tpp[i];
	dp[u]=max(dp[u],val[u]);//这里
	for(auto v:g[u]){
		dp[v]=max(dp[v],dp[u]+val[v]);
	}
}

这里必须取一个max,因为不然在后续的dp过程中会被初始化覆盖。

2025/1/21 20:50
加载中...