h3>Problem Statement
Joisino is about to compete in the final round of a certain programming competition.
In this contest, there are \(N\) problems, numbered \(1\) through \(N\).
Joisino knows that it takes her \(T_i\) seconds to solve problem \(i(1≦i≦N)\).
In this contest, a contestant will first select some number of problems to solve. Then, the contestant will solve the selected problems. After that, the score of the contestant will be calculated as follows:
- (The score) $=$ (The number of the pairs of integers $L$ and $R$ $(1≦L≦R≦N)$ such that for every $i$ satisfying $L≦i≦R$, problem $i$ is solved) - (The total number of seconds it takes for the contestant to solve the selected problems)
Note that a contestant is allowed to choose to solve zero problems, in which case the score will be $0$.
Also, there are $M$ kinds of drinks offered to the contestants, numbered $1$ through $M$. If Joisino takes drink $i(1≦i≦M)$, her brain will be stimulated and the time it takes for her to solve problem $P_i$ will become $X_i$ seconds. Here, $X_i$ may be greater than the length of time originally required to solve problem $P_i$. Taking drink $i$ does not affect the time required to solve the other problems.
A contestant is allowed to take exactly one of the drinks before the start of the contest. For each drink, Joisino wants to know the maximum score that can be obtained in the contest if she takes that drink. Your task is to write a program to calculate it instead of her.
Constraints
- All input values are integers.
- $1≦N≦3*10^5$
- $1≦T_i≦10^9$
- (The sum of $T_i$) $≦10^{12}$
- $1≦M≦3*10^5$
- $1≦P_i≦N$
- $1≦X_i≦10^9$
Input
The input is given from Standard Input in the following format:
$N$ $T_1$ $T_2$ $...$ $T_N$ $M$ $P_1$ $X_1$ $P_2$ $X_2$ $:$ $P_M$ $X_M$
Output
For each drink, print the maximum score that can be obtained if Joisino takes that drink, in order, one per line.
Sample Input 1
5 1 1 4 1 1 2 3 2 3 10
Sample Output 1
9 2
If she takes drink $1$, the maximum score can be obtained by solving all the problems.
If she takes drink $2$, the maximum score can be obtained by solving the problems $1,2,4$ and $5$.
Sample Input 2
12 1 2 1 3 4 1 2 1 12 3 12 12 10 9 3 11 1 5 35 6 15 12 1 1 9 4 3 10 2 5 1 7 6
Sample Output 2
34 35 5 11 35 17 25 26 28 21
首先，在一个 + 号后面增加括号是没有用的。
容易发现，在减号后面至多增加两个括号。增加了更多括号，可以拆成增加两个括号的形式。
定义 \(dp_{i,j}\) 为前 \(i\) 个数，目前有多少个左括号未匹配，然后枚举是否填括号即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],f[N],t;
long long dp[N][3];
char c;
int main()
{
memset(dp,-0x7f,sizeof(dp));
scanf("%d%d",&n,&a[1]),dp[1][0]=a[1];
for(int i=2;i<=n;i++)
scanf(" %c%d",&c,a+i),f[i]=c=='+'? 1:-1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=2;j++)
{
t=j==1? -1:1;
dp[i][j]=dp[i-1][j]+t*f[i]*a[i];
if(j!=2)
dp[i][j]=max(dp[i-1][j+1]-t*f[i]*a[i],dp[i][j]);
if(j&&f[i]==-1)
dp[i][j]=max(dp[i][j],dp[i-1][j-1]-t*f[i]*a[i]);
}
}
printf("%lld",max(dp[n][0],max(dp[n][1],dp[n][2])));
}