第3回ドワンゴからの挑戦状 本戦 A - 計算ドリル

企業コンテスト

俺のrated500埋めの最後の問題がこれ
atcoderでこういう実装ゲーはかなり珍しい

問題

'0'〜'9'、'+'、'-' のみからなる文字列sが与えられる
これをk文字まで書き換えて得られる、逆ポーランド記法で計算できる正しい文字列のうち、計算結果の最大値を求めよ

1 <= |s| <= 52
0 <= k <= |s|

解法

メモ化しながら区間dp
数式の一番最後の文字は '+' か '-' である必要があり、それ以外の部分は2つの式に分けることができるってのがポイント
この区切りとそれぞれの区間に割り振るkを全探索して更新していく
詳細は↓のコメントの通り

string s;
int n, k, dp[55][55][55][2];
bool fin[55][55][55][2];
const int M = 10000;

// [l,r]をk文字まで変えたときの最(b?大:小)値
int rec(int l, int r, int x, bool b) {
	if (fin[l][r][x][b]) return dp[l][r][x][b];
	fin[l][r][x][b] = 1;
	int &res = dp[l][r][x][b];
	res = (b ? -M : M);
	// どう変えても正しい式にならない場合
	if ((r-l+1)%2==0) return res;
	// 1桁の場合
	if (l==r) {
		if (x) res = (b ? 9 : 0);
		else if (isdigit(s[l])) res = s[l]-'0';
		return res;
	}
	// 一番右の文字は+か-にする
	int xp = x - (s[r]!='+'), xm = x - (s[r]!='-');
	// 2つの式の和の最大値は (最大)+(最大) or (最大)-(最小)
	if (b) {
		reps(i,l,r-1) {
			rep(j,xp+1) {
				int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xp-j,1);
				if (tx!=-M && ty!=-M) chmax(res, tx+ty);
			}
			rep(j,xm+1) {
				int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xm-j,0);
				if (tx!=-M && ty!=M) chmax(res, tx-ty);
			}
		}
	}
	// 最小値は (最小)+(最小) or (最小)-(最大)
	else {
		reps(i,l,r-1) {
			rep(j,xp+1) {
				int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xp-j,0);
				if (tx!=M && ty!=M) chmin(res, tx+ty);
			}
			rep(j,xm+1) {
				int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xm-j,1);
				if (tx!=M && ty!=-M) chmin(res, tx-ty);
			}
		}
	}
	return res;
}

signed main() {
	cin >> k >> s;
	n = s.size();
	int res = rec(0,n-1,k,1);
	if (res==-M) cout << "NG" << endl;
	else cout << "OK" << endl << res << endl;
}

https://beta.atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_a