20191024 csp-s模拟T2（区间dp）

T2 jerry

2.1 题目描述
众所周知，Jerry鼠是一只非常聪明的老鼠。Jerry聪明到它可以计算64位有符号整形数字的加减法。现在，Jerry写下了一个只由非负整数和加减号组成的算式。它想给这个算式添加合法的括号，使得算式的结果最大。这里加减法的运算优先级相同，和我们在日常生活中接触到的一样，当没有括号时，先算左边的，再算右边的。比如，算式$((1 + 2) + 3 (4 5)) + 6$((1+2)+3(45))+6是合法的，但是$)1 + 2($)1+2(和$( )1 + 2以及 (1) + 2$()1+2以及(1)+2都是不合法的。
2.2 输入描述
第一行一个整数$T$T，代表数据组数。
接下来，共有$T$T组数据，每组的格式如下：
第一行一个整数$n$n，代表数字的个数。
接下来一行共$2n-1$2n−1个符号或非负整数，组成一个由空格隔开的算式。
2.3 输出描述
一行一个整数，代表添加括号后，算式最大的可能结果。
2.4 输入样例&输出样例
#1输入
1
3
5 - 1 - 3
#1输出
7
#2输入
2 4
1 - 1 - 1 - 3
1 - 1 - 1 + 3 4
#2输出
4
4
2.5 样例说明
对于第一个样例：
$5-(1-3)=7$5−(1−3)=7
对于第二个样例：
$1-(1-1-3)=4$1−(1−1−3)=4
$1-(1-(1+3))=4$1−(1−(1+3))=4
2.6 数据范围
对于全部的数据，$n\leq 10^5,\sum n\leq 2\times 10^5,2\leq n.$n≤105,∑n≤2×105,2≤n.

思路：
可以发现：
1.只在负数前加括号对答案有影响。
2.最多加两层括号即可构造出最大值。
——>证明：
若$s[i]\lt 0$s[i]<0且在$i$i前添加括号：对于$i$i后连续正数$s[i+1]-s[j]$s[i+1]−s[j]求和时取值必为负。对于$i$i后第一个负数$s[j+1]$s[j+1]，在其前面添加括号至$i$i后第二个负数$s[k]$s[k]，不难发现，在求和时$j+1至k$j+1至k的数全取正。对于之后的数都如此操作，都能取正。

首先将所有连续正数合并，此时相邻两负数间最多间隔一个正数，求出后缀和$sum$sum，从后向前dp。
有状态转移方程：
$if(s[i]\ge0) dp[i]=dp[i+1]+s[i];$if(s[i]≥0)dp[i]=dp[i+1]+s[i];
$if(s[i]\lt0)\lbrace$if(s[i]<0){
$if(s[i+1]\lt0) dp[i]=max(dp[i+1]+s[i],s[i]+sum[i+1]);$if(s[i+1]<0)dp[i]=max(dp[i+1]+s[i],s[i]+sum[i+1]);
$if(s[i+1]\ge0) dp[i]=max(dp[i+1]+s[i],s[i]-s[i+1]+sum[i+2]);$if(s[i+1]≥0)dp[i]=max(dp[i+1]+s[i],s[i]−s[i+1]+sum[i+2]);
$\rbrace$}

代码：

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define re register

inline char cha(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline long long in{
	long long s=0,f=1;char x;
	for(x=cha();!isdigit(x);x=cha())	if(x=='-')	f=-1;
	for( ;isdigit(x);x=cha())	s=(s<<1)+(s<<3)+(x&15);
	return s*f;
}

inline void out(long long x){
	if(x<0){
		putchar('-');
		x=-x;
	}	
	if(x/10)	out(x);
	putchar(x%10|48);
}

const long long A=2e5+5;
const long long INF=-1e18;
long long t,n;
char ch;
long long p[A];
long long dp[A];
long long a[A],tot,sum[A];

inline void scan(){
	n=in;
	p[1]=in;
	for(re int i=2;i<=n;++i){
		while(ch!='-'&&ch!='+')	ch=cha();
		p[i]=in*((ch=='+')?1:-1);
		ch='0';
	}
}

inline void work(){
	for(re int i=tot;i>=1;--i){
		dp[i]=dp[i+1]+a[i];
		if(a[i]<0){
			if(a[i+1]<=0)	dp[i]=max(dp[i],a[i]+sum[i+1]);
			if(a[i+1]>0)	dp[i]=max(dp[i],a[i]-a[i+1]+sum[i+2]);
		}
	}
	printf("%lld\n",dp[1]);
}

inline void clean(){
	memset(p,0,sizeof(p));
	memset(a,0,sizeof(a));tot=0;
	memset(sum,0,sizeof(sum));
	memset(dp,0,sizeof(dp));
}

inline void prepare(){
	long long all=0;
	for(re int i=1;i<=n;++i){
		if(p[i]>=0)	all+=p[i];
		if(p[i]<0){
			if(all){
				a[++tot]=all;
				all=0;
			}
			a[++tot]=p[i];
		}
	}
	if(all)	a[++tot]=all;
	for(re int i=tot;i>=1;--i)
		sum[i]=sum[i+1]+abs(a[i]);
}

signed main(){
	//freopen("jerry.in","r",stdin);
	//freopen("jerry.out","w",stdout);
	t=in;
	while(t--){
		clean();
		scan();
		prepare();
		work();
	}
	return 0;
}