kmjp's blog

競技プログラミング参加記です

AtCoder ARC #066 : E - Addition and Subtraction Hard

気づいてしまえば簡単なのだが。
http://arc066.contest.atcoder.jp/tasks/arc066_c

問題

N個の整数と、間に2項間演算子の+・-のいずれかがが計(N-1)個ある数式が与えられる。
この式に任意に括弧を追加できる場合、この式の値を最大化せよ。

解法

"+"の直後に開き括弧を置いても意味がない。
逆に-の直後は必ず開き括弧を置くとする。
また、整数の直後では任意の数の開き括弧を閉じられるとする。
(-の後に括弧を置きたくない場合は、直後の整数の直後に閉じてしまえば実質置かない場合と同じ結果を得られる)

各整数は、開いたまま閉じてない開き括弧の数の偶奇によって足されるか引かれるか決まる。
よって、以下の状態を考え、f(N,0)を求めればそれが解。
f(i,p) := まだ開き括弧がp個残っている状態i項目までの整数に対し数式の値を計算したときの最大値

ただこのままだと上記f(i,p)はO(N^2)とおり考える必要がありTLEおよびMLEする。
ただし、実際は3個以上の開き括弧を考える必要はない。
A-(B-(C-(D...という式はA-(B-(C))-(D... というように3つ目の開き括弧が生じる場合手前に2個括弧を閉じても同じ値が得られるためである。
よってf(i,0)、f(i,1)、f(i,2)を順次DPで求めていけばよい。

int N;
ll dp[101010][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>x;
	memset(dp,0xcf,sizeof(dp));
	dp[0][0]=x;
	
	FOR(i,N-1) {
		cin>>s>>x;
		
		ll T[3];
		if(s=="+") {
			T[0]=dp[i][0];
			T[1]=dp[i][1];
			T[2]=dp[i][2];
		}
		else {
			T[0]=T[2]=dp[i][1];
			T[1]=max(dp[i][0],dp[i][2]);
		}
		dp[i+1][2] = T[2]+x;
		dp[i+1][1] = max(dp[i+1][2], T[1]-x);
		dp[i+1][0] = max(dp[i+1][1], T[0]+x);
	}
	
	cout<<*max_element(dp[N-1],dp[N-1]+3)<<endl;
	
}

まとめ

この問題、本番検索したら海外の掲示板(stackoverflowだったか)に書かれていたけどO(N^2)解法だったので採用できなかった。