zoj1094，请用python代码解决，需要在zoj上获得ac
链接：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827364593
OK，过了，是我之前想多了，其实更简单
代码如下：
import sys
s = sys.stdin.readlines()
n = int(s[0].strip())
matrixes = dict()
for i in range(1, n+1):
name, row, col = s[i].strip().split()
matrixes[name] = (int(row), int(col))
for i in range(n+1, len(s)):
exp = s[i].strip()
if exp == "": break
if len(exp) == 1: print(0)
else:
ans = 0
q = list()
for i in exp:
if i.isalpha(): q.append(list(matrixes[i]))
elif i == ")":
b = q.pop()
a = q.pop()
if a[1] == b[0]:
ans += a[0]*b[0]*b[1]
a[1] = b[1]
q.append(a)
else:
print("error")
break
else:
print(ans)
import re
n = int(input())
inp = [input().split() for _ in range(n)]
dic = {v[0]:[int(v[1]),int(v[2])] for v in inp}
while True:
try:
inp = input().strip()
if not re.search(r'[^\(\)]{2}',inp):
print(0)
else:
ans = 0
while re.search(r'[^\(\)]{2}',inp):
s = re.findall(r'[^\(\)]{2}',inp)
for i in range(len(s)):
a,b = list(s[i])
if dic[a][1] != dic[b][0]:
ans = 'error'
break
else:
ans += dic[a][0] * dic[a][1] * dic[b][1]
dic[str(i)] = [dic[a][0],dic[b][1]]
inp = re.sub(r'\(?' + s[i] + r'\)?',str(i),inp)
if ans == 'error':
break
print(ans)
except:
break
以下答案由GPT-3.5大模型与博主波罗歌共同编写：
题目描述
给定一个数列 $a_1,a_2,\cdots,a_n(1\leq n\leq 100)$，再给定一个整数 $m(1\leq m\leq 100)$，以及 $p,q\in R,p>q$，$Fib(i)$ 表示第 $i$ 个斐波拉契数，斐波拉契数列的定义为：
$Fib(1)=Fib(2)=1$
$\forall i\geq 3$，$Fib(i)=Fib(i-1)+Fib(i-2)$
定义 $\text{msum}(a)$ 表示数组 $a$ 的最大子段和，也就是选定 $a$ 中的一个区间，使得该区间的元素之和最大。
记 $S_i=\text{msum}(a_1,\cdots,a_i)$。
定义 $\text{mavg}(a)$ 表示数组 $a$ 的最大平均值，也就是选定 $a$ 中的一个区间，使得该区间的平均值最大。
记 $A_i$ 表示 $S_1$ 至 $S_i$ 中最大的 $j$，使得 $\frac{S_{j}-S_i}{j-i}> q$，若不存在这样的 $j$，则 $A_i=-1$。
记 $B_i$ 表示 $S_1$ 至 $S_i$ 中最小的 $j$，使得 $\frac{S_{j}-S_i}{j-i}< p$， 若不存在这样的 $j$，则 $B_i=-1$。
记 $C_i$ 表示 $S_1$ 至 $S_n$ 中最小的 $j$，使得 $S_i-S_j\geq m$，若不存在这样的 $j$，则 $C_i=-1$。
输入格式
第 1 行：$3$ 个用空格隔开的实数 $p,q,m$。
第 2 行：$1$ 个正整数 $n$，表示数列 $a$ 的元素个数。
第 3 行：$n$ 个用空格隔开的整数 $a_1,a_2,\cdots,a_n$，分别表示 $a_i$ 的值。
输出格式
输出共 $4$ 行。
第 $1$ 行：$-1$ 或者 $A_1$，表示 $a$ 数组的前 $1$ 个数所构成数组的 $A$ 数组的值。
第 $2$ 行：$-1$ 或者 $B_1$，表示 $a$ 数组的前 $1$ 个数所构成数组的 $B$ 数组的值。
第 $3$ 行：$-1$ 或者 $A_2,\cdots,A_n$，表示 $a$ 数组的前 $2\sim n$ 个数所构成的数组 $A$，中间用一个空格隔开。
第 $4$ 行：$-1$ 或者 $B_2,\cdots,B_n$，表示 $a$ 数组的前 $2\sim n$ 个数所构成的数组 $B$，中间用一个空格隔开。
解题思路
对于这道题，题目将计算最大子段，可以用最大子段和算法，将求连续子段权值和最大的问题转化为正负交替的最大和子段问题，使用动态规划即可。求这个问题后，计算每个连续子段的平均值。
此外，题目中涉及到一些有意思的技巧：
多个O(n)指标问题
对于一个长度为n的数列，如果要求它的绝对分位点（比如中位数），分位点左边的数看作1个指标，右边的数看作另一个指标，这种问题需要中间做一些转化，通过O(n)预处理，将所有位置的指标值都还原成一个第i个数左边/右边的某个指标。
对于中位数问题，使用中位数至关重要，对于非中位数问题，重要性取决于题目具体要求。
这种做法可以大大降低问题的复杂度。
类似的，本题中求解A,B,C，也可以将其转化为三个1D指标（即左边/右边有多少个元素符合题目要求）
把条件中涉及到的Fib数列转化为指标
条件(p > q，S[i] - S[j] >= m)难以直接求取，考虑将条件转化为Fib数列的形式:
(a[j] - a[i]) / (j - i) < p
(a[j] - a[i]) / (j - i) > q
(a[j] - a[i]) > m
观察条件，发现用这三个式子表示平移后，得到的是一个类似大小关系的式子。
不难想到将a数组看成一条数轴。对于(a[j] - a[i]) / (j - i) < p斜率小于p，即小于p的点构成的区域，这个区域的下界是用直线$y = p \times x + k$切到y轴得到的点，由于这里只需要知道最靠左的点，因此可以手动求出第一个点y > px的位置，以后每个点和上一个点的位置之间的斜率都不会低于p，因此这部分预处理的时间复杂度是O(n)的。
对于(a[j] - a[i]) / (j - i) > q的点，同样，从矩形的右上角（即a[i],i）开始往左斜率逐渐降低，直至低于q。手动求出右上角的斜率，以后每个点和上一个点的位置之间的斜率都不会超过q，因此这部分预处理的时间复杂度也是O(n)的。
处理C数组，也可以类似地转化成一个大S形，从两端开始，不能超过斜率为m的直线，靠边的点加入三角形。
python代码
如果我的回答解决了您的问题，请采纳！