第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-4 算法训练 结点选择
前言
最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是dp分析能力了,所以就主要目标定在这里,最近的题目会很散,很多,基本上都是网罗全网的一些dp练习题进行二次训练,准备比赛的学生底子薄的先不建议看啊,当然,脑子快的例外,可以直接跳过之前的一切直接来看即可,只需要你在高中的时候数学成绩还可以那就没啥问题,其实,dp就是规律总结,我们只需要推导出对应题目的数学规律就可以直接操作,可能是一维数组,也可能是二维数组,总体来看二维数组的较多,但是如果能降为的话建议降为,因为如果降为起来你看看时间复杂度就知道咋回事了,那么在这里祝大家能无序的各种看明白,争取能帮助到大家。
算法训练 结点选择
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
问题描述
有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?
输入格式
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行,每行描述树上的一条边。
输出格式
输出一个整数,代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
样例说明
选择3、4、5号点,权值和为 3+4+5 = 12 。
数据规模与约定
对于20%的数据, n <= 20。
对于50%的数据, n <= 1000。
对于100%的数据, n <= 100000。
权值均为不超过1000的正整数。
题解,与划分领地差不多的权值计算。
C语言
#include <stdio.h> #include <string.h> #define _Max 100010 #define max(a, b) a > b ? a : b struct point { int v, next; //v指向这条边的另一个结点(父结点),next指向子结点 } edge[_Max * 2]; //一条边记录两次,分别以一个点做记录 int head[_Max]; int M; int dp[_Max][2]; //添加一个边 void addEdge(int from, int to) { //from结点 edge[M].v = to; edge[M].next = head[from]; //为-1则定位叶结点,否则,指向另外一条边 head[from] = M++; //指向他的一条边,增加结点 //to结点 edge[M].v = from; edge[M].next = head[to]; //为-1则定位叶结点,否则,指向另外一条边 head[to] = M++; //指向他的一条边,增加结点 return ; } //深度遍历,先深入到叶子结点,然后一层一层往上回升,一直到根结点,即第一个结点(初始pre为-1是因为根结点没有父结点,用-1表示) void dfs(int x, int pre) { int i = head[x], v; for (; i != -1; i = edge[i].next) //i != -1说明有子结点,则遍历子结点,否则为叶子结点 { v = edge[i].v; if (pre == v) //如果指向的子结点和父结点重合,则说明这个结点是叶子结点,不需要进一步dp { continue; } dfs(v, x); //x可以理解为父结点 //深度遍历到最里面的叶子结点的父结点 如果父结点选择,则子结点不选择,否则子结点可能选择或者不选择,但是要比较两者哪个大选择哪个 dp[x][1] += dp[v][0]; // 父结点(选) += 子结点(不选) dp[x][0] += max(dp[v][0], dp[v][1]); // 父结点(不选) += max(子结点(不选),子结点(选)) } return ; } int main(int argc, const char * argv[]) { int i, n, s, t, tmp; scanf("%d", &n); M = 0; memset(head, -1, sizeof(head)); //初始化每个结点都是独立的没有子结点 memset(dp, 0, sizeof(dp)); //输入权值,并且记录在dp[i][1]上,i表示第i个结点,1代表取了这个结点 for (i = 1; i <= n; i++) { scanf("%d", &dp[i][1]); } //输入边,并且添加edge,一个边添加两个edge for (i = 1; i < n; i++) { scanf("%d %d", &s, &t); addEdge(s, t); } dfs(1, -1); //深度优先遍历,从第一个结点开始遍历 tmp = max(dp[1][0], dp[1][1]); //求出最大的权值和 printf("%d\n", tmp); return 0; }
C++语言
#include<stdio.h> const int NO=1000005; int dp[NO][2]; int du[NO]; int first[NO],next[NO],v[NO],num=1; bool mark[NO]; int n,a; int t[NO],tip,top; int max(int a,int &b){return a>b?a:b;} void input(int &num) { num=0; char ch=getchar(); while(ch<'0'||'9'<ch) ch=getchar(); while('0'<=ch&&ch<='9') { num=10*num+ch-'0'; ch=getchar(); } } void add(int &a,int &b) { v[num]=b; next[num]=first[a]; first[a]=num++; v[num]=a; next[num]=first[b]; first[b]=num++; } int work() { int i; while(tip<top) { a=t[tip++]; mark[a]=1; for(i=first[a];i!=-1;i=next[i]) if(mark[v[i]]) { dp[a][0]+=max(dp[v[i]][0],dp[v[i]][1]); dp[a][1]+=dp[v[i]][0]; } else if(--du[v[i]]==1) t[top++]=v[i]; } return max(dp[a][0],dp[a][1]); } int main() { int i,a,b; scanf("%d",&n); for(i=1;i<=n;i++) input(dp[i][1]),first[i]=-1; for(i=1;i<n;i++) input(a),input(b),add(a,b),du[a]++,du[b]++; for(i=1;i<=n;i++) if(du[i]==1) t[top++]=i; printf("%d\n",work()); return 0; }
Java语言
import java.io.IOException; import java.util.Scanner; import java.util.Stack; public class Main { private static int[][] dp; private static int[][] tree; private static Stack<Element> stack = new Stack<>(); static class Element { int start; // 节点编号 int root; // 节点的父亲节点的编号 int count; // 计数器,用来记录节点第count个孩子节点 public Element(int start, int root, int count) { this.start = start; this.root = root; this.count = count; } } public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n + 2][2]; tree = new int[n + 2][100]; for (int i = 0; i < n; i++) { dp[i + 1][1] = sc.nextInt(); } for (int i = 0; i < n - 1; i++) { int point1 = sc.nextInt(); int point2 = sc.nextInt(); createTree(point1, point2); } sc.close(); dfs2(1, 0); // 从创建的数的根节点(即第1个顶点,0表示根节点的父母节点)开始进行DFS遍历 System.out.println(Math.max(dp[1][0], dp[1][1])); } /** * @param point1 表示输入的第point1个节点,不是节点权值 * @param point2 表示输入的第point2的节点,不是节点权值 * @apiNote 由于题目仅仅给出边的说明,并未说明两个节点谁是父母节点,所以以下有两种情形 */ static void createTree(int point1, int point2) { int i = 0; // 当第point1个节点为父母节点时 while (tree[point1][i] != 0) i++; tree[point1][i] = point2; // 如果第point1个节点已经有孩子了,再增加一个孩子 int j = 0; // 当第point2个节点为父母节点时 while (tree[point2][j] != 0) j++; tree[point2][j] = point1; } /** * @param start 开始对树进行DFS遍历的开始节点,为具体节点位置,不是节点权值 * @param root 为第start个节点的直接父母节点位置,root = 0表示根节点的父母节点 */ // 老dfs,会因为递归次数过多导致系统堆栈溢出报错,导致最后三个测试案例运行错误 static void dfs(int start, int root) { int child = tree[start][0]; // 第start个节点的第1个孩子节点 for (int i = 0; child != 0; i++) { child = tree[start][i]; if (child != root) // 防止出现start的孩子成为start的父亲情况 { dfs(child, start); dp[start][1] += dp[child][0]; // 当第child个节点没有孩子节点时,开始回溯 dp[start][0] += Math.max(dp[child][0], dp[child][1]); } } } // 新dfs,自己创建一个堆栈来存储相关信息,就不需要使用递归了,也就不会产生堆栈溢出问题 static void dfs2(int start, int root) { stack.push(new Element(start, root, 0)); // 初始化第一个点压入堆栈,开始堆栈操作 while (!stack.isEmpty()) { Element temp = stack.peek(); // 查看栈顶信息 int child = tree[temp.start][temp.count]; // 找到点的孩子节点 temp.count++; // 计数器加1 if (child != 0) { if (child != temp.root) { stack.push(new Element(child, temp.start, 0)); continue; } } else { dp[temp.root][1] += dp[temp.start][0]; dp[temp.root][0] += Math.max(dp[temp.start][1], dp[temp.start][0]); stack.pop(); } } } }
Python语言
这题的难度还是不小的呢。
class Vertex(): def __init__(self,id): self.id=id self.connect=[] self.visited=False def addEdge(self,vertex): self.connect.append(vertex.id) def dfs(num): stack=[num] numList[num].visited=True while stack: node = stack[-1] for n in numList[node].connect: if not numList[n].visited: stack.append(n) numList[n].visited=True break else: if stack.pop() != 1: dp[stack[-1]][0] += max(dp[node][0],dp[node][1]) dp[stack[-1]][1] += dp[node][0] numList={} n=int(input()) values = input().split() values = [int(x) for x in values] dp=[[0 for i in range(2)] for i in range(n+1)] for i in range(1,n+1): dp[i][1]=values[i-1] numList[i]=Vertex(i) for i in range(n-1): pre,vertex=map(int,input().split()) numList[pre].addEdge(numList[vertex]) numList[vertex].addEdge(numList[pre]) dfs(1) print(max(dp[1][0],dp[1][1]))
总结
虽然四种语言的答案都给了,并且基本上算是最优解,但是理解起来还是很困难的,我们需要逐一的抽丝剥茧,当我们不会解题思路的时候就先学习别人的,学到手了就是自己的了。