SRM654 Div2 Hard / SuccessiveSubtraction2

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13699
配列aが与えられ、それはa[0]-a[1]-...-a[n]という式を表す。この式の中に括弧を2組まで入れた時式の結果の最大値答える。

解法

Editorial一部改変。　http://apps.topcoder.com/wiki/display/tc/SRM+654

const int INF = 1e9;
int dp[2001][3][3];
class SuccessiveSubtraction2 {
public:
	int n;
	vector<int> a;
	//何個目、括弧が開いているか、残りの括弧
	int func(int p, int open, int remaining) {
		int& res = dp[p][open][remaining];
		if (res == -INF) {
			if (p == n) {
				//終わり
				res = 0;
			} else {
				//open==0 括弧がない そのまま減算
				int x = ((open % 2 == 0) ? -a[p] : a[p]);
				if (remaining > 0 && open == 0) {
					//括弧の残りが1個以上　&&　開いた括弧がない　→　開けられる
					res = max(res, x + func(p + 1, open + 1, remaining - 1));
				}
				if (open > 0) {
					//括弧開いているので閉じられる
					res = max(res, func(p, open - 1, remaining));
				}
				//何もしない
				res = max(res, x + func(p + 1, open, remaining));
			}
		}
		return res;
	}

	vector<int> calc(vector<int> b, vector<int> p, vector<int> v) {
		n = b.size();
		a = b;

		vector<int> ans(p.size());
		for (int i = 0; i < p.size(); i++) {
			//初期化
			for (int i = 0; i < 2001; i++) {
				for (int j = 0; j < 3; j++) {
					for (int k = 0; k < 3; k++) {
						dp[i][j][k] = -INF;
					}
				}
			}
			//更新
			a[p[i]] = v[i];
			//1つ目(0-indexed)、閉じている、残り2回
			//最初のはどうやっても加算固定
			ans[i] = a[0] +  func(1, 0, 2);
		}
		return ans;
	}

};
<||