第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-4 算法训练 结点选择
目录
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-4 算法训练 结点选择
前言
算法训练 结点选择
C语言
C 语言
Java语言
Python语言
总结
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是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语言
代码语言：javascript复制#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("%dn", tmp);
return 0;
}C 语言
代码语言：javascript复制#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("%dn",work());
return 0;
}Java语言
代码语言：javascript复制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语言
这题的难度还是不小的呢。
代码语言：javascript复制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]))总结
虽然四种语言的答案都给了，并且基本上算是最优解，但是理解起来还是很困难的，我们需要逐一的抽丝剥茧，当我们不会解题思路的时候就先学习别人的，学到手了就是自己的了。
