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,0Sl..r为合法括号序列otherwise
你可以将序列分成若干非空子段，定义整个序列的美丽度为每段的w(l,r)w(l , r)w(l,r)之和。
求美丽度最大为多少。
输入格式
第一行一个整数nnn。
第二行一个字符串，代表括号序列。
第三行代表序列aaa。
输出格式
第一行一个整数，表示最大的美丽度。
输入输出样例 #1
输入 #1
5 ()(() 1 3 2 3 5输出 #1
4输入输出样例 #2
输入 #2
10 ()((())()) 2 4 1 7 3 2 8 4 9 5输出 #2
8说明/提示
样例解释 #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 | 无 | 303030 |
| Subtask #2 | ≤105\le 10 ^ 5≤105 | 无 | 202020 |
| Subtask #3 | ≤3×106\le 3 \times 10 ^ 6≤3×106 | 括号序列为()()…()()()\dots()()()…() | 151515 |
| Subtask #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++实现
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=3e6+5,inf=1e18;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);cin>>n>>S;for(inti=1;i<=n;++i)cin>>a[i],b[i]=(S[i-1]=='(');for(inti=1;i<=n;++i)if(!b[i]&&r)lst[i]=st[r--];elseif(b[i])st[++r]=i;for(inti=0;i<=n;++i)f[i]=c[i]=-inf;f[0]=0;for(inti=1;i<=n;++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]);}}cout<<f[n];return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
