小行星

用户名：theasteroid

访问量：1297

签　名：

等　　级
排　　名	13261
经　　验	932
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校	芜湖大学
专　　业

　　自我简介：

TA的其他文章

利用完全二叉树性质，非广搜得到答案
浏览：102

蓝桥杯2019年第十届省赛真题-人物相关性分析（滑动窗口）
浏览：294

蓝桥杯2019年第十届省赛真题-扫地机器人(二分)
浏览：397

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

树形dp逆向求值

　　作者: 小行星　　　　发表时间：2022-04-05 17:34:06 浏览：514　|　评论：0　

原题链接：蓝桥杯2020年第十一届省赛真题-作物杂交

`````cpp
#include <iostream>
#include <algorithm> 
#include <set> 
#define ll long long

/*
思路：
	首先得明确我们要的是什么：k号种子 
	
	每个种子都有两种状态：有、没有，如果是有那么0开销获得
		如果没有，那么需要 递归 取min 求获得该种子所需最小开销，而一旦求出，那么该值便固定，可无限供应其他需要此种子的使用。 
		
	定义：f[i]为获取当前种子的最小时间
		以目标k号种子为根节点建立一颗多叉树，可以使用set<pair<int,int>> chil[MAXN]存放儿子节点
	 使用子元素松弛f[k]: f[k] = min(f[k], max(f[son[k][0]], f[son[k][1]]);
	
	到这里整体思路已经结束了，可以使用dfs进行树形dp，整体类似记忆化搜索，使用vis记录当前编号i是否已经计算出开销，时间复杂度为线性 
		 
*/
const int MAXN = 2e3 + 9, INF = 1e9;
int n, m, k, t, f[MAXN], w[MAXN];
bool vis[MAXN];
std::set<std::pair<int,int> > st[MAXN];

void dfs(int rt){
	if(vis[rt]) return;
	for(auto it : st[rt]){
		dfs(it.first);
		dfs(it.second);
		f[rt] = std::min(f[rt], std::max(f[it.first], f[it.second]) + std::max(w[it.first], w[it.second]) );
	}
	vis[rt] = true; // 别忘记，每求出一个rt就要更新状态
} 
int main(){
	std::cin >> n >> m >> k >> t;
	for(int i = 1; i <= n; i++) {
		f[i] = INF;
		std::cin >> w[i];
	}
	
	while(m--){
		int x; std::cin >> x;
		vis[x] = true, f[x] = 0;
	}
	
	int u, v, w;
	while(k--){
		std::cin >> u >> v >> w;
		if(u > v) std::swap(u, v); // 让u<v方便后续去重 
		st[w].insert({u, v});
	}
	
	dfs(t);
	
	std::cout << f[t];
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小行星

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

树形dp逆向求值

评论区

精彩推荐

Minesweeper （C语言代码）

IP判断（C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

printf基础练习2 （C语言代码）

最长单词（C语言代码）

C二级辅导-阶乘数列（C语言代码）

printf基础练习2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

小行星

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

树形dp逆向求值

评论区

精彩推荐

Minesweeper （C语言代码）

IP判断 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

printf基础练习2 （C语言代码）

最长单词 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

printf基础练习2 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

　　评论区

IP判断（C语言代码）

最长单词（C语言代码）

C二级辅导-阶乘数列（C语言代码）