网站开发页面静态化技术,谷歌seo外贸推广,手机端wordpress模板,如何建一个营销网站备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一#xff1a;游戏 试题二#xff1a;石子合并 试题三#xff1a;密码脱落 试题四#xff1a;能量项链 试题一#xff1a;游戏
【题目描述】 玩家一和玩家二共同玩一个小游戏。给定一个包含 N 个…备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一游戏 试题二石子合并 试题三密码脱落 试题四能量项链 试题一游戏
【题目描述】 玩家一和玩家二共同玩一个小游戏。给定一个包含 N 个正整数的序列。由玩家一开始双方交替行动。每次行动可以在数列的两端之中任选一个数字将其取走并给自己增加相应数字的分数。双方的初始分都是 0 分当所有数字都被取完时游戏结束。分更高的一方获胜。请计算如果双方都采取最优策略进行游戏则游戏结束时双方的得分各是多少。
【输入格式】 第一行包含整数 N。 后面若干行包含 N 个整数表示这个序列。注意每行不一定恰好包含一个数。
【输出格式】 共一行两个整数分别表示玩家一和玩家二的最终得分。
【数据范围】 2≤N≤100 数列中的数字的取值范围为 [1,200]
【输入样例】
6
4 7 2 9
5 2
【输出样例】
18 11
【解题思路】 采用一般的DP分析方法f[i][j][k]表示玩家j在区间i~j的最大取值。 所以考虑如何状态转移它肯定是由对手1-k选左边的或者选右边的得到也即是f[i][j][k] max(f[i][j][k]s[j] - s[i] - f[i1][j][1-k] a[i]s[j-1]-s[i-1] - f[i][j-1][1-k] a[j] )。最后的答案为f[1][n][0]s[j]-f[1][n][0]。
【Python程序代码】
n int(input())
a,s [0],[0]*(n10)
while True:try:tep list(map(int,input().split()))a tepexcept:break
f [[[0]*2 for i in range(210)] for j in range(210)]
for i in range(1,n1):s[i] s[i-1]a[i]
for i in range(1,n1):for k in [0,1]:f[i][i][k]a[i]f[i-1][i][k]max(a[i],a[i-1])
for i in range(n,0,-1):for j in range(i1,n1):for k in [0,1]:# 取右边f[i][j][k] max(f[i][j][k], s[j-1]-s[i-1] - f[i][j-1][1-k] a[j])# 取左边f[i][j][k] max(f[i][j][k], s[j]-s[i] - f[i1][j][1-k] a[i])
print(f[1][n][0],s[j]-f[1][n][0]) 试题二石子合并
【题目描述】 设有 N 堆石子排成一排其编号为 1,2,3,…,N。每堆石子有一定的质量可以用一个整数来描述现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。例如有 4 堆石子分别为 1 3 5 2 我们可以先合并 1、2堆代价为 4得到 4 5 2 又合并 1、2堆代价为 9得到 9 2 再合并得到 11总代价为 491124如果第二步是先合并 2、32 堆则代价为 7得到 4 7最后一次合并代价为 11总代价为 471122。问题是找出一种合理的方法使总的代价最小输出最小代价。
【输入格式】 第一行一个数 N 表示石子的堆数 N。 第二行 N 个数表示每堆石子的质量(均不超过 1000)。
【输出格式】 输出一个整数表示最小代价。
【数据范围】 1≤N≤300
【输入样例】
4
1 3 5 2
【输出样例】
22
【解题思路】 采用区间DP的方法f[i][j]表示将区间i-j合并需要付出的最小代价所以先枚举区间长度然后枚举做端点如果左端点为1则赋值f[i][j]0否则枚举区间断点k在i1~j-1的范围状态转移方程为f[i][j] min(f[i][j]f[i][k] f[k1][j] s[j]-s[i-1])最后的答案为f[1][n]
【Python程序代码】
n int(input())
a [0] list(map(int,input().split()))
s [0]*(n10)
for i in range(1,n1):s[i] s[i-1]a[i]
f [[1e9]*(n10) for _ in range(n10)]
for le in range(1,n1):i 1while ile-1n:j ile-1if le1:f[i][j]0i1continuefor k in range(i,j):f[i][j] min(f[i][j],f[i][k]f[k1][j]s[j]-s[i-1])i1
print(f[1][n])
试题三密码脱落
【题目描述】 X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。仔细分析发现这些密码串当初应该是前后对称的也就是我们说的镜像串。由于年代久远其中许多种子脱落了因而可能会失去镜像的特征。你的任务是给定一个现在看到的密码串计算一下从当初的状态它要至少脱落多少个种子才可能会变成现在的样子。
【输入格式】 共一行包含一个由大写字母ABCD构成的字符串表示现在看到的密码串。
【输出格式】 输出一个整数表示至少脱落了多少个种子。
【输入样例】
ABDCDCBABC
【输出样例】
3
【解题思路】 其实就是求最长回文子序列可以采用区间DP的方法先枚举区间长度然后枚举区间左端点如果区间长度为1则f[i][j]1否则当s[i]s[j]时f[i][j] max(f[i1][j]f[i][j-1])当s[i]s[j]时f[i][j] max(f[i][j]f[i1][j-1]2).最后答案为n - f[0][n-1]
【Python程序代码】
f [[0]*(1010) for _ in range(1010)]
s input()
n len(s)
for le in range(1,n1):i 0while ile-1n:j ile-1if le1:f[i][j]1else:f[i][j] max(f[i 1][j], f[i][j - 1])if s[i] s[j]:f[i][j] max(f[i][j], f[i 1][j - 1] 2)i 1
print(n-f[0][n-1])试题四能量项链
【题目描述】 在 Mars 星球上每个 Mars 人都随身佩带着一串能量项链在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子这些标记对应着某个正整数。并且对于相邻的两颗珠子前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样通过吸盘吸盘是 Mars 人吸收能量的一种器官的作用这两颗珠子才能聚合成一颗珠子同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m尾标记为 r后一颗能量珠的头标记为 r尾标记为 n则聚合后释放的能量为 m×r×nMars 单位新产生的珠子的头标记为 m尾标记为 n。需要时Mars 人就用吸盘夹住相邻的两颗珠子通过聚合得到能量直到项链上只剩下一颗珠子为止。显然不同的聚合顺序得到的总能量是不同的请你设计一个聚合顺序使一串项链释放出的总能量最大。例如设 N444 颗珠子的头标记与尾标记依次为 (23)(35)(510)(102)。我们用记号 ⊕⊕ 表示两颗珠子的聚合操作(j⊕k)表示第 jk 两颗珠子聚合后所释放的能量。则第 4、14、1 两颗珠子聚合后释放的能量为(4⊕1)10×2×360。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)10×2×310×3×510×5×10710。
【输入格式】 输入的第一行是一个正整数 N表示项链上珠子的个数。 第二行是 N 个用空格隔开的正整数所有的数均不超过 1000第 i 个数为第 i 颗珠子的头标记当 iN 时第 i 颗珠子的尾标记应该等于第 i1 颗珠子的头标记第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。 至于珠子的顺序你可以这样确定将项链放到桌面上不要出现交叉随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序。
【输出格式】 输出只有一行是一个正整数 E为一个最优聚合顺序所释放的总能量。
【数据范围】 4≤N≤100, 1≤E≤2.1×109
【输入样例】
4
2 3 5 10
【输出样例】
710
【解题思路】 首先这个这是一个环如何处理环的首尾相接呢可以在原数组的末尾在复制一个一样的数组也就是构建出每一个首尾。最后答案应该为枚举i in [1,n]res max(resf[i][in])。采用区间DP的方法先枚举区间长度然后枚举区间左端点然后枚举断点k。状态转移方程为f[ll][r] max(f[l][r]f[l][k] f[k][r] w[l]*w[k]*[r])。
【Python程序代码】
n int(input())
w list(map(int,input().split()))
w [0] w w
f [[0]*(2*n5) for _ in range(2*n5)]
for le in range(2,n2):l 1while lle-1(n1):r lle-1if le2:f[l][r]0else:for k in range(l1,r):f[l][r] max(f[l][r], f[l][k] f[k][r] w[l]*w[k]*w[r])l1
res 0
for l in range(1,n1):res max(res,f[l][ln])
print(res)
