打卡信奥刷题（3411）用C++实现信奥题 P10115 [LMXOI Round 1] Placer

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

输入 #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

对于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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容