题目描述
定义合法数学表达式
E
E
E 为一个数或两个合法数学表达式中间加上一个加或减运算符，并且在外面加上一对括号。
给定一个合法数学表达式，将其中加减运算符用
?
?
? 待定，最多指派
p
p
p 个加法运算符和
q
q
q 次减法运算（保证
p
+
q
=
?
p + q = \ ?
p+q= ? 的个数），求给定的数学表达式的最大值。
数据范围
1
≤
∣
E
∣
≤
1
⋅
1
0
4
,
1
≤
m
i
n
(
p
,
q
)
≤
100
1 \leq |E| \leq 1 \cdot 10^4, 1 \leq min (p, q) \leq 100
1≤∣E∣≤1⋅104,1≤min(p,q)≤100
题解报告
首先可以构造一棵树来表达各个表达式之间的运算关系。
具体来说，树的每棵子树表示一个合法数学表达式，
叶子节点表示一个具体的数（也是合法数学表达式，与子树的含义不冲突），
每个非叶子节点仅有两个儿子节点（因为一个加法或减法运算符只能连接两个数学表达式），
并且需要指派一个加法或减法运算符，表示通过该运算符直接将左子树代表的数学表达式与右子树代表的数学表达式进行一次加法或减法运算。构造过程类似于
K
r
u
s
k
a
l
Kruskal
Kruskal 重构树。
至于实现方式，可以用一个栈来保存最新的数学表达式，
从左到右遍历给定的数学表达式时，遇到一个数字就把他放入栈中；
遇到一个
"
)
"
")"
")" 就在树上新建一个节点，左儿子和右儿子为栈顶两个元素在树上对应的节点；
弹出栈顶两个元素，同时把这个新的节点也放入栈中，两个数学表达式合并成了一个。
利用这种方法，遍历完给定的数学表达式后，栈中一定只剩下一个元素，且该元素正好是构造的树的根节点编号。
构造完这棵树后，考虑在这棵树上进行树上
d
p
dp
dp。
定义
m
x
[
i
]
[
j
]
mx[i][j]
mx[i][j] 表示第
i
i
i 个节点所代表的子树内使用
j
j
j 次加法运算符的最大运算结果，
m
n
[
i
]
[
j
]
mn[i][j]
mn[i][j] 表示第
i
i
i 个节点所代表的子树内使用
j
j
j 次加法运算符的最大运算结果，
对于每个叶子节点，有 $mx[i][0] = mn[i][0] = $ 该叶子节点代表的具体的数；
对于每个非叶子节点，
-
当指派节点
i
i
i 为加法运算符时，考虑
m
x
[
i
]
[
j
]
mx[i][j]
mx[i][j] 与
m
n
[
i
]
[
j
]
mn[i][j]
mn[i][j] 状态如何转移。
暴力枚举左子树使用加法运算符次数
k
1
k_1
k1 从
0
0
0 到
j
−
1
j - 1
j−1，
右子树使用加法运算符次数
k
2
k2
k2 满足
k
1
+
k
2
+
1
=
j
k1 + k2 + 1 = j
k1+k2+1=j，即
k
2
=
j
−
k
1
−
1
k2 = j - k1 - 1
k2=j−k1−1，
于是有
m
x
[
i
]
[
j
]
=
m
a
x
k
1
=
0
,
1...
j
−
1
(
m
x
[
l
s
]
[
k
1
]
+
m
x
[
r
s
]
[
j
−
k
1
−
1
]
)
mx[i][j] = \underset{k1 = 0,1 ...j - 1} {max} (mx[ls][k1] + mx[rs][j - k1 - 1])
mx[i][j]=k1=0,1...j−1max(mx[ls][k1]+mx[rs][j−k1−1])，
其中
l
s
ls
ls 和
r
s
rs
rs 分别表示节点
i
i
i 的左儿子和右儿子；
类似的有
m
n
[
i
]
[
j
]
=
m
i
n
k
1
=
0
,
1...
j
−
1
(
m
n
[
l
s
]
[
k
1
]
+
m
n
[
r
s
[
j
−
k
1
−
1
]
)
mn[i][j] = \underset {k1 = 0, 1...j - 1}{min} (mn[ls][k1] + mn[rs[j - k1 - 1])
mn[i][j]=k1=0,1...j−1min(mn[ls][k1]+mn[rs[j−k1−1])。
-
当指派节点
i
i
i 为减法运算符时，
m
x
[
i
]
[
j
]
mx[i][j]
mx[i][j] 与
m
n
[
i
]
[
j
]
mn[i][j]
mn[i][j] 状态的转移过程与上述类似，
主要区别是转移方程应修改为：（注意枚举上限不同了）
m
x
[
i
]
[
j
]
=
m
a
x
k
1
=
0
,
1...
j
(
m
x
[
l
s
]
[
k
1
]
−
m
n
[
r
s
]
[
j
−
k
1
−
1
]
)
mx[i][j] = \underset{k1 = 0,1 ...j} {max} (mx[ls][k1] - mn[rs][j - k1 - 1])
mx[i][j]=k1=0,1...jmax(mx[ls][k1]−mn[rs][j−k1−1])；
m
n
[
i
]
[
j
]
=
m
i
n
k
1
=
0
,
1...
j
(
m
n
[
l
s
]
[
k
1
]
−
m
x
[
r
s
[
j
−
k
1
−
1
]
)
mn[i][j] = \underset {k1 = 0, 1...j}{min} (mn[ls][k1] - mx[rs[j - k1 - 1])
mn[i][j]=k1=0,1...jmin(mn[ls][k1]−mx[rs[j−k1−1])。
由于转移过程是
O
(
p
)
O(p)
O(p) 的，每个节点有
p
p
p 种状态，所以复杂度是
O
(
n
p
2
)
O(np^2)
O(np2)。
题目中还有个限制条件：
m
i
n
(
p
,
q
)
≤
100
min(p, q) \leq 100
min(p,q)≤100，
当
p
≤
100
p \leq 100
p≤100 时，上述做法显然不会
T
L
E
TLE
TLE；
当仅有
q
≤
100
q \leq 100
q≤100 时，只需把状态设置成减法运算符的使用次数，并对转移方式做细节上的修改即可。
所以考虑限制条件后的复杂度应为
O
(
n
⋅
m
i
n
(
p
,
q
)
2
)
O(n \cdot min (p, q)^2)
O(n⋅min(p,q)2)。
AC代码：
#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N = 1e5 + 5;
const int M = 1e2 + 5;
int n, p, q, tot;
void init () {}
void charming () {
init ();
string s;
cin >> s, n = s.size ();
cin >> p >> q;
vector <int> isLeaf (N), siz (N);
vector <array <int, 2> > ch (N);
vector <vector <int> > mx (N, vector <int> (M, -INT_MAX));
vector <vector <int> > mn (N, vector <int> (M, INT_MAX));
vector <int> stk;
for (int i = 0, d, lid, rid; i < n; ++i) {
if (s[i] == '(') {
continue;
}
else if (s[i] == '?') {
continue;
}
else if (s[i] == ')') {
++tot;
rid = stk.back ();
stk.pop_back ();
lid = stk.back ();
stk.pop_back ();
ch[tot][0] = lid, ch[tot][1] = rid;
siz[tot] = siz[lid] + siz[rid] + 1;
stk.emplace_back (tot);
}
else {
++tot;
isLeaf[tot] = true;
d = s[i] - '0';
mn[tot][0] = mx[tot][0] = d;
stk.emplace_back (tot);
}
}
auto DFS = [&] (auto && me, int cur) -> void {
if (isLeaf[cur]) return;
int &lid = ch[cur][0], &rid = ch[cur][1];
me (me, lid), me (me, rid);
if (p <= 100) {
for (int i = 1; i <= min (siz[cur], p); ++i) {
for (int j = max (0ll, i - 1 - siz[rid]); j <= min (i - 1, siz[lid]); ++j) {
mx[cur][i] = max (mx[cur][i], mx[lid][j] + mx[rid][i - 1 - j]);
mn[cur][i] = min (mn[cur][i], mn[lid][j] + mn[rid][i - 1 - j]);
}
}
for (int i = 0; i <= min (siz[cur], p); ++i) {
for (int j = max (0ll, i - siz[rid]); j <= min (i, siz[lid]); ++j) {
mx[cur][i] = max (mx[cur][i], mx[lid][j] - mn[rid][i - j]);
mn[cur][i] = min (mn[cur][i], mn[lid][j] - mx[rid][i - j]);
}
}
}
else {
for (int i = 0; i <= min (siz[cur], q); ++i) {
for (int j = max (0ll, i - siz[rid]); j <= min (i, siz[lid]); ++j) {
mx[cur][i] = max (mx[cur][i], mx[lid][j] + mx[rid][i - j]);
mn[cur][i] = min (mn[cur][i], mn[lid][j] + mn[rid][i - j]);
}
}
for (int i = 1; i <= min (siz[cur], q); ++i) {
for (int j = max (0ll, i - 1 - siz[rid]); j <= min (i - 1, siz[lid]); ++j) {
mx[cur][i] = max (mx[cur][i], mx[lid][j] - mn[rid][i - 1 - j]);
mn[cur][i] = min (mn[cur][i], mn[lid][j] - mx[rid][i - 1 - j]);
}
}
}
};
int rt = stk[0];
DFS (DFS, rt);
if (p <= 100) cout << mx[rt][p] << endl;
else cout << mx[rt][q] << endl;
}
signed main () {
charming ();
return 0;
}
后记
这个题目其实主要分两个部分，建树和
d
p
dp
dp，然后两个部分其实都不是很难，
r
a
t
i
n
g
rating
rating 却有
2300
2300
2300。拿来给今年集训队
d
i
v
2
div2
div2 的训，做出来的人数还可以吧。
