P10115 [LMXOI Round 1] Placer题目背景LMX 最近迷上了括号序列她尤其钟爱合法括号序列。LMX 为了检验 HQZ 的真诚于是她出一道题准备考验下 HQZ。题目描述LMX 给出了一个长度为nnn括号序列SSS以及一个长度为nnn的序列aia_iai​。定义w(l,r){ar−al,Sl..r为合法括号序列 0otherwisew(l,r) \begin{cases} a_r-a_l, S_{l..r} \text{为合法括号序列}\\ \ 0 \text{otherwise} \end{cases}w(l,r){ar​−al​,0​Sl..r​为合法括号序列otherwise​你可以将序列分成若干非空子段定义整个序列的美丽度为每段的w(l,r)w(l , r)w(l,r)之和。求美丽度最大为多少。输入格式第一行一个整数nnn。第二行一个字符串代表括号序列。第三行代表序列aaa。输出格式第一行一个整数表示最大的美丽度。输入输出样例 #1输入 #15 ()(() 1 3 2 3 5输出 #14输入输出样例 #2输入 #210 ()((())()) 2 4 1 7 3 2 8 4 9 5输出 #28说明/提示样例解释 #1原串可以划分成三个区间[1,2],[3,3],[4,5][1,2],[3,3],[4,5][1,2],[3,3],[4,5]。贡献为(a2−a1)0(a5−a4)(3−1)0(5−3)4(a_2-a_1)0(a_5-a_4)(3-1)0(5-3)4(a2​−a1​)0(a5​−a4​)(3−1)0(5−3)4子任务编号nnn特殊性质分值Subtask #1≤5000\le 5000≤5000无303030Subtask #2≤105\le 10 ^ 5≤105无202020Subtask #3≤3×106\le 3 \times 10 ^ 6≤3×106括号序列为()()…()()()\dots()()()…()151515Subtask #4≤3×106\le 3 \times 10 ^ 6≤3×106无353535对于100%100\%100%的数据1≤ai≤1091\le a_i \le 10^91≤ai​≤109。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN3e65,inf1e18;intn,a[N],lst[N],r;intf[N],st[N],c[N];boolb[N];string S;signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnS;for(inti1;in;i)cina[i],b[i](S[i-1]();for(inti1;in;i)if(!b[i]r)lst[i]st[r--];elseif(b[i])st[r]i;for(inti0;in;i)f[i]c[i]-inf;f[0]0;for(inti1;in;i){f[i]f[i-1];if(lst[i]){c[i]max(c[lst[i]-1],f[lst[i]-1]-a[lst[i]]);f[i]max(c[i]a[i],f[i]);}}coutf[n];return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容