皇宫看守
2023/5/24 1:22:06
本文主要是介绍皇宫看守,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。
皇宫各个宫殿的分布,呈一棵树的形状,宫殿可视为树中结点,两个宫殿之间如果存在道路直接相连,则该道路视为树中的一条边。
已知,在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况,还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。
大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。
输入格式
输入中数据描述一棵树,描述如下:
第一行 n,表示树中结点的数目。
第二行至第 n+1 行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号 i,在该宫殿安置侍卫所需的经费 k,该结点的子结点数 m,接下来 m 个数,分别是这个结点的 m 个子结点的标号 r1,r2,…,rm。
对于一个 n 个结点的树,结点标号在 1 到 n 之间,且标号不重复。
输出格式
输出一个整数,表示最少的经费。
数据范围
1≤n≤1500
输入样例
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0
输出样例
25
样例解释
在2、3、4结点安排护卫,可以观察到全部宫殿,所需经费最少,为 16 + 5 + 4 = 25。
题目分析
代码实现
#include<iostream> #include<cstring> #include<algorithm> using namespace std; #define int long long const int N=1505; int h[N],e[2*N],ne[2*N],idx; //dp[i][0]表示结点i由其父节点放置的守卫看守 //dp[i][1]表示结点i由其子节点放置的守卫看守 //dp[i][2]表示结点i由该节点放置的守卫看守 int dp[N][3],cost[N],vis[N]; void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++; } void dfs(int u){ dp[u][2]=cost[u]; int sum=0; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; dfs(j); //由于dp[u][0]表示结点u由其父节点的守卫看守,所以结点u上不需要放置守卫 //所以结点u的子节点一定不能被其父节点u看守,所以不存在dp[j][0]这种状态 //所以只取dp[j][1]和dp[j][2]中的最小值即可 dp[u][0]+=min(dp[j][1],dp[j][2]); //由于dp[u][2]表示结点u由其自己的守卫看守,所以结点u上一定放置了守卫 //所以结点u的子节点三种状态都存在,所以需要取三种状态的最小值 dp[u][2]+=min(dp[j][0],min(dp[j][1],dp[j][2])); sum+=min(dp[j][1],dp[j][2]); } //dp[u][1]的情况比较复杂,其表示结点u由其子节点放置的守卫看守 //所以结点u上一定没有放置守卫,所以其子节点也只有dp[j][1]和dp[j][2]两种状态 //首先计算所有子节点的最小开销和sum //然后逐个遍历判断让哪个子节点作为看守父节点u的结点 //求取出该子节点后的开销最小值 dp[u][1]=0x3f3f3f3f; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; dp[u][1]=min(dp[u][1],sum+dp[j][2]-min(dp[j][1],dp[j][2])); } } signed main(){ int n,root=-1; cin>>n; memset(h,-1,sizeof h); for(int i=0;i<n;i++){ int x,y,k,c; cin>>x>>c>>k; cost[x]=c; while(k--){ cin>>y; add(x,y); vis[y]=1; } } for(int i=1;i<=n;i++)if(!vis[i])root=i; dfs(root); //由于根节点没有父节点,故根节点只有dp[root][1]和dp[root][2]两种状态 //所以求该两种状态的最小值即可 cout<<min(dp[root][1],dp[root][2])<<endl; return 0; }
这篇关于皇宫看守的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-15Springboot应用的多环境打包学习
- 2024-10-15Springboot应用的生产发布学习
- 2024-10-15创建Springboot项目学习:新手入门教程
- 2024-10-15创建springboot项目学习:新手入门教程
- 2024-10-14Java创业学习:新手入门教程
- 2024-10-14JAVA创业学习:新手入门教程
- 2024-10-14Java创业学习:从零开始的Java编程教程
- 2024-10-14Java对接阿里云智能语音服务学习
- 2024-10-14JAVA对接阿里云智能语音服务学习教程
- 2024-10-14Java副业学习:从入门到实战的简单教程