Codeforces 935E Fafa and Ancient Mathematics（表达式转树 + 树型DP）

题目链接 Codeforces Round #465 (Div. 2) Problem E

题意给定一个表达式，然后用$P$个加号和$M$个减号填充所有的问号（保证问号个数等于$P + M$）

　　求可以形成的表达式的最大值。

先把表达式转成一棵树，然后在树上DP。

题目保证了$min(P, M) <= 100$, 为了提高效率，我们选择用少的运算符号作为DP的第二维。

对$P$和$M$的大小关系进行分类讨论。

当$P < M$时，

设$f[i][j]$表示$i$代表的子树里面填$j$个加号能得到的结果的最大值。

$c[i][j]$表示$i$代表的子树里面填$j$个减号能得到的结果的最小值。

那么转移就是

$f[x][i+j+1] = max(f[x][i+j+1], f[l][i] + l[r][j])$

$f[x][i+j] = max(f[x][i+j], f[l][i] - c[r][j])$

$c[x][i+j+1] = min(c[x][i+j+1], c[l][i] + c[r][j])$

$c[x][i+j] = min(c[x][i+j], c[l][i] - f[r][j])$

当$P > M$时，

设$f[i][j]$表示$i$代表的子树里面填$j$个加号能得到的结果的最大值。

$c[i][j]$表示$i$代表的子树里面填$j$个减号能得到的结果的最小值。

设个时候转移方程为

$f[x][i+j] = max(f[x][i+j], f[l][i] + l[r][j])$

$f[x][i+j+1] = max(f[x][i+j+1], f[l][i] - c[r][j])$

$c[x][i+j] = min(c[x][i+j], c[l][i] + c[r][j])$

$c[x][i+j+1] = min(c[x][i+j+1], c[l][i] - f[r][j])$

程序里把两种情况合起来写了，看起来更加简洁。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const int N = 1e4 + 10;

const int M = 105;

const int inf = 1e9;

char st[N];

int val[N];

int p, m, n;

int f[N][M], c[N][M];

vector <int> v[N];

stack <int> stk;

inline void upmax(int &a, int b){ a = max(a, b);}

inline void upmin(int &a, int b){ a = min(a, b);}

void dfs(int x, int t){

	rep(i, 0, M - 1) f[x][i] = -inf, c[x][i] = inf;

	if (val[x]){

		f[x][0] = c[x][0] = val[x];

		return;

	}

	int l = v[x][0], r = v[x][1];

	dfs(l, t), dfs(r, t);

	rep(i, 0, M - 1) if (f[l][i] > -inf){

		rep(j, 0, M - 1) if (f[r][j] > -inf){

			upmax(f[x][i + j + t], f[l][i] + f[r][j]);

			upmax(f[x][i + j + (t ^ 1)], f[l][i] - c[r][j]);

			upmin(c[x][i + j + t], c[l][i] + c[r][j]);

			upmin(c[x][i + j + (t ^ 1)], c[l][i] - f[r][j]);

		}

	}

}

int main(){

	scanf("%s%d%d", st, &p, &m);

	for (int i = 0; st[i]; ++i){

		if (st[i] == '(') stk.push(++n);

		else if (st[i] == ')'){

			int t = stk.top();

			stk.pop();

			if (!stk.empty()) v[stk.top()].push_back(t);

		}

		else if (st[i] >= '1' && st[i] <= '9'){

			if (stk.empty()) return 0 * printf("%d\n", st[i] - '0');

			v[stk.top()].push_back(++n);

			val[n] = st[i] - '0';

		}

	}

	dfs(1, p < m);

	printf("%d\n", f[1][min(p, m)]);

	return 0;

}

巴特西

Codeforces 935E Fafa and Ancient Mathematics（表达式转树 + 树型DP）

最新文章

热门文章