蓝桥杯-2023年第十四届省赛真题Python（E-F）

E：保险箱

【问题描述】

        小蓝有一个保险箱，保险箱上共有 n 位数字。

        小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加 1 或减少 1。

        当某位原本为 9 或 0 时可能会向前（左边）进位/退位，当最高位（左边第 一位）上的数字变化时向前的进位或退位忽略。

        例如：

        00000 的第 5 位减 1 变为 99999 ；

        99999 的第 5 位减 1 变为 99998 ；

        00000 的第 4 位减 1 变为 99990 ；

        97993 的第 4 位加 1 变为 98003 ；

        99909 的第 3 位加 1 变为 00009 。

        保险箱上一开始有一个数字 x，小蓝希望把它变成 y，这样才能打开它，问小蓝最少需要操作的次数。

【输入格式】

        输入的第一行包含一个整数 n 。

        第二行包含一个 n 位整数 x 。

        第三行包含一个 n 位整数 y 。

【输出格式】

        输出一行包含一个整数表示答案。

【样例输入】

5
12349
54321

【样例输出】

11

 【解析及代码】

        题目意思就是，对于在一个位的数字x[i]，要让它变成y[i]，每个位的数字所用的操作数都最少，那么总的ans也是最小的，很明显的dp问题，操作有三种情况（不进不退、进、退），那么我们首先要把最右边最先处理的数初始化（三种情况），然后后续逐步更新左边的数的情况，就三种，然后要选右数过来到自己的时候的最小情况，直到找到最左边的数，为了方便可以倒叙存储，直到最后输出min(dp[n][0],dp[n][1],dp[n][2])最小方案。

#不进不退0，进1，退2

dp[i][0]=min{dp[i-1][0],dp[i-1][1],dp[i-1][2]}+dp[i][0]

dp[i][1]=min{dp[i-1][0],dp[i-1][1],dp[i-1][2]}+dp[i][1]

dp[i][2]=min{dp[i-1][0],dp[i-1][1],dp[i-1][2]}+dp[i][2]

要注意的是进退位之后数字会变

n=int(input())
#列表倒叙存数组
l1=[0]+list(map(int,input()))[::-1] #input()返回的是str类型是可迭代对象
l2=[0]+list(map(int,input()))[::-1]
#三种情况n个数字
dp=[[0]*3 for i in range(n+1)]
#初始化第一位
dp[1][0]=abs(l2[1]-l1[1]) #不进不退
dp[1][1]=10-l1[1]+l2[1] #进
dp[1][2]=10+l1[1]-l2[1] #退
 
#开始动态规划
#如果l1[i-1]的数字是进位到l1[i],那l1[i]的数字就要+1，否则-1
for i in range(2,n+1):
    dp[i][0] = min(abs(l2[i] - l1[i]) + dp[i - 1][0], abs(l2[i] - 1 - l1[i]) + dp[i - 1][1],abs(l2[i] + 1 - l1[i]) + dp[i - 1][2])
    dp[i][1] = min(10 - l1[i] + l2[i] + dp[i - 1][0], 9 - l1[i] + l2[i] + dp[i - 1][1],11 - l1[i] + l2[i] + dp[i - 1][2])
    dp[i][2] = min(10 + l1[i] - l2[i] + dp[i - 1][0], 11 + l1[i] - l2[i] + dp[i - 1][1],9 + l1[i] - l2[i] + dp[i - 1][2])
 
print(min(dp[n][0], dp[n][1], dp[n][2]))
 

F：树上选点

【问题描述】

        给定一棵树，树根为 1，每个点的点权为Vi。

        你需要找出若干个点Pi，使得：

        1. 每两个点Px,Py互不相邻；

        2. 每两个点Px,Py与树根的距离互不相同；

        3. 找出的点的点权之和尽可能大。

        请输出找到的这些点的点权和的最大值。

【输入格式】

        输入的第一行包含一个整数 n 。

        第二行包含 n − 1 个整数  ，相邻整数之间使用一个空格分隔，分别表示第 2 至 n 个结点的父结点编号。

        第三行包含 n 个整数 ，相邻整数之间使用一个空格分隔，分别表示每个结点的点权。

【输出格式】

        输出一行包含一个整数表示答案。

【样例输入】

5
1 2 3 2
2 1 9 3 5

【样例输出】

11

【解析及代码】

        权值最大值，有父子结构，树形存储，明显的树形dp问题，则需要从叶子节点开始遍历，然后逐步往上直到根节点。所以我们需要构造深度表，遍历每一层深度的每个节点，每个节点有两个不同的选择（选这个节点/不选这个节点）用dp表示就是dp[j][0]/dp[j][1]表示不选或选。因为条件限制不能相邻的，所以该节点选or不选会影响下一层的某的节点选or不选，用state来表示下一层分三种情况（下一层不选，下一层选最大 ，下一层选次大），然后根据j节点的选or不选来比较下一层怎么选能有最大权值，最后就比较根节点选或不选哪个大（dp[1][0],de[1][1]）

#树形DP问题
n=int(input()) #节点的数量n
fa=[0,0]+list(map(int,input().split())) #存储父节点
v=[0]+list(map(int,input().split()))#存储权值
 
#每个节点深度，每一个深度有什么节点，最大深度
dep=[0]*(n+1)
dep_node=[[] for i in range(n+1)]
deep_max=0
 
#完善上面的变量
for i in range(1,n+1):
    dep[i]=dep[fa[i]]+1 #该节点的深度等于父节点的深度+1
    dep_node[dep[i]].append(i) #在对应深度加上节点
    deep_max=max(dep[i],deep_max)#更新最大深度
 
#创建dp表，那么一个节点分两种情况，选这个节点还是不选,不选0，选1
dp=[[0]*2 for i in range(n+1)] #dp[i][0] #表示i节点不选
 
state=[0,0,0] #state存储的是下一层的三种情况[下一层不选，下一层选最大值，下一层选次大值]
##因为很重要一点就是可能别人两层的数就比你三层的大，这就是state[0]的意义
 
#开始dp,树形dp从叶子开始，就是倒着遍历
for i in range(deep_max,0,-1):
    for j in dep_node[i]: #遍历这个深度的节点
        #第一种情况就是j节点不选,那这层要么不要，要么要最大值
        dp[j][0]=max(dp[state[0]][0],dp[state[1]][1])
        #第二种情况就是j节点选
        #选的话要判断j是不是下一层最大值的父节点
        if fa[state[1]] == j:  # 如果下一层的最大值结点是j的子结点, 则选择max(非j子结点的最大值, 不选的最大值结点)
            dp[j][1] = v[j] + max(dp[state[0]][0], dp[state[2]][1])
        else:  # max(下一层的最大值结点, 不选的最大值结点)
            dp[j][1] = v[j] + max(dp[state[0]][0], dp[state[1]][1])
 
    state = [0, 0, 0]
    #更新state
    for j in dep_node[i]:  # 求深度为i的dp[j][0]和dp[j][1]的最大值
        if dp[state[0]][0] < dp[j][0]:
            state[0] = j
        if dp[state[1]][1] < dp[j][1]:
            state[1] = j
 
    for j in dep_node[i]:  # 求i深度下和选最大值结点非共同父结点的次最大值结点
        if fa[state[1]] != fa[j] and dp[state[2]][1] < dp[j][1]:
            state[2] = j
 
print(max(dp[1][0], dp[1][1]))