当前位置：首页 > news >正文

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

news 2026/6/26 11:16:27

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

输入输出样例 #2

输入 #2

10 ()((())()) 2 4 1 7 3 2 8 4 9 5

输出 #2

说明/提示

样例解释 #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;}