本题会有大规模测试用例，用深度优先搜索可能会超出迭代次数上限。也许可以通过手动指定迭代次数上限来解决这个问题，但我选择维护动态规划列表。 本质上和前两道打家劫舍没有什么区别，难度虚高了。 n = int(input()) pts = list(map(int, input().split())) # points fas = list(map(int, input().split())) # fathers # 建树：sons[idx]是idx的子节点。节点编号从0开始。 sons = dict() for idx in range(1,n): fa = fas[idx] - 1 if fa ...

对区间动态规划。 n = int(input()) aa = list(map(int, input().split())) bb = list(map(int, input().split()))[::-1] # dp[i][j]是这一族问题中输入为aa[i:j+1]和bb[i:j+1]时的解。 dp = [[0 for j in range(n)] for i in range(n)] # 初始化：最小的子问题就是n=1的情况，总共只有一种可能。 for idx in range(n): dp[idx][idx] = aa[idx] * bb[0] # 动态规划：只有两种可能，要么当前区间...

对python来说，本题真正的难点在于l很大时如何不超时。 为此需要运用数论做一些粗浅的算法优化。 实际上还有很多能抠的细节没有抠，因为在python上的运行速度已经比较令人满意了，再去深究一些不能改变运算量数量级的地方意义不大。 注：由irises1412提供的答案应该是错误的，它通不过示例自测。 # 对python来说，本题真正的难点在于l很大时如何不超时。 l = int(input()) s, t, m = list(map(int, input().split())) sts = list(map(int, input().split())) sts = sorted(sts) # ...

二维动态规划。 def match(p, s): m, n = len(p), len(s) # 初始化边界： # 1、dp[0][0] = True，空模式空字符串，匹配成功； # 2、dp[0][j] = False，空模式无法匹配非空字符串； # 3、dp[i][0]不确定，只有模式为星号*时，才能匹配空字符串，即模式p前i个字符均为星号*。 dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for i in range(1, m + 1): if i == 1: dp[i][0] = p[i - 1] == "...

当做一般动态规划来做。 tar = int(input()) # dp[i] 是和为i+1所需的完全平方数的最小数量 dp = [float('inf') for _ in range(tar)] # 初始化：记录完全平方数的位置 for i in range(int(tar**0.5)): dp[(1+i)**2-1] = 1 sqrs = [] # 动态规划迭代 for i in range(tar): if dp[i] == 1: # i+1是完全平方数 sqrs.append(i+1) else: # choice是加上某个完全平方数之后等于i+1的所有数字，即i+1是在某个choic...

用辗转相除法计算最大公约数，再计算最小公倍数。 while True: try: a,b = map(int,input().split()) prod=a*b while min(a,b)!=0: if a < b: b=b%a else: a=a%b print(int(prod/max(a,b))) except: break

分治法：将问题分为两种可能的情形处理，收集分类信息和处理每一种情形都只可以利用打家劫舍（一）的算法完成。 n = int(input()) nums = list(map(int, input().strip().split())) # 处理输入极短的情况，避免指针越界 if len(nums) == 1: print(nums[0]) elif len(nums) in [2,3]: print(max(nums)) elif len(nums) == 4: print(max(nums[0]+nums[2], nums[1]+nums[3])) # 主要情况 else: a,b = num...

描述： 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 输入描述： 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。 输出描述： 输出最大子矩阵的大小。 解答： 首先定义一个函数cslms来计算一维数组的连续子数组最大和，这也是这套题里的一道. def cslms(ns: list)...

主程序将数组分割成若干个不含0的子数组，从而使的子数组的乘积不会是0. 在分割过程中，为了方便把正数用1表示，负数用0表示。 函数ml意为一个不含0的数组ll的乘积为正数的最长连续子数组点长度max_len。这又可以按ll中有多少负数分成三种情况： Case 1：含有偶数个负数，全部乘起来一定是正数； Case 2：含有1个负数，把数组分割成前后两段，哪段长那段就是乘积为正数的最长连续子数组； Case 3：含有奇数个负数且把数组分割成至少四段，这时要么舍弃第一段、要么舍弃最后一段不加入我们想要的乘积为正数的最长连续子数组，哪段短就舍弃哪段。 # negative number index n...

以下用maxnum表示以x结尾的连续子数组中乘积最大者。minnum同理。用res持续maxnum迭代过程中取到的最大值。 以x.next结尾的连续子数组的乘积除以x.next一定是1或者某个以x结尾的连续子数组的乘积，从而在minnum和maxnum之间并且不等式的两个端点都可以取到。因此，新的maxnum一定是x * maxnum (若x>0,maxnum>0)或者 x * minnum (若x<0)或者 x (若maxnum<0,x>0)。这就形成了动态规划的迭代步骤。 nums = list(map(int, input().split())) res =...

分最长对称子串的长度是奇数（k）还是偶数（l）处理。 ss = input() l,i = 2,0 # l=2n while (0<=i) and (i< len(ss)-l+1): if ss[i:i+l] == ss[i:i+l][::-1]: l += 2 i -= 2 if i > 0 else 1 # avoid i back to -1 i += 1 k,i = 3,0 # k=2n+1 while (0<=i) and (i< len(ss)-k+1): if ss[i:i+k] == ss[i:i+k][::-1]: k += 2 i -= 2 i...

计算通项之后利用列表推导式直接打印结果即可： m = int(input()) print('+'.join([str(s) for s in range(m**2-m+1,m**2+m,2)]))