Codeforces935E Fafa and Ancient Mathematics(表达式转树 + 树型DP)

it2022-05-05  109

题目链接  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; }

 

  

 

 

转载于:https://www.cnblogs.com/cxhscst2/p/8486123.html


最新回复(0)