codeforces 935E 建树，dp

E. Fafa and Ancient Mathematics

题意：
给出一串加减表达式，括号可以互相匹配。其中有 p 个加号， m 个减号，问最后的结果最大可能是多少。 min(p,m)<=100
tags：
题目数据范围给了提示。。
先按括号匹配建好树，dp1[i][j], dp2[i][j] 表示结点 i 子树下面有 j 个数量较小符号的最大最小值，然后在 dfs 的过程中更新即可。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 10005, M = 1e5+10;

int n, m, a[N], cnt[M], tot, tr[M][2];
ll  dp1[M][105], dp2[M][105];
bool flag;
int mn;
char s[N];
stack< int > Stack;
void pushup(int ro) {
    int lson = tr[ro][0], rson = tr[ro][1];
    if(!flag)
    {
        rep(i,0,cnt[ro])
            for(int j=0; j<=cnt[lson] && j<=i; ++j)
                if(i-j<=cnt[rson])
        {
            dp1[ro][i] = max(dp1[ro][i], dp1[lson][j]+dp1[rson][i-j]);
            dp2[ro][i] = min(dp2[ro][i], dp2[lson][j]+dp2[rson][i-j]);
        }
        rep(i,0,cnt[ro]-1)
            for(int j=0; j<=cnt[lson] && j<=i; ++j)
                if(i-j<=cnt[rson])
        {
            dp1[ro][i+1] = max(dp1[ro][i+1], dp1[lson][j]-dp2[rson][i-j]);
            dp2[ro][i+1] = min(dp2[ro][i+1], dp2[lson][j]-dp1[rson][i-j]);
        }
    }
    else
    {
        rep(i,0,cnt[ro])
            for(int j=0; j<=cnt[lson] && j<=i; ++j)
                if(i-j<=cnt[rson])
        {
            dp1[ro][i] = max(dp1[ro][i], dp1[lson][j]-dp2[rson][i-j]);
            dp2[ro][i] = min(dp2[ro][i], dp2[lson][j]-dp1[rson][i-j]);
        }
        rep(i,0,cnt[ro]-1)
            for(int j=0; j<=cnt[lson] && j<=i; ++j)
                if(i-j<=cnt[rson])
        {
            dp1[ro][i+1] = max(dp1[ro][i+1], dp1[lson][j]+dp1[rson][i-j]);
            dp2[ro][i+1] = min(dp2[ro][i+1], dp2[lson][j]+dp2[rson][i-j]);
        }
    }
}
void solve(int ro, int l, int r)
{
    if('1'<=s[l] && s[l]<='9') return ;
    solve(tr[ro][0], l+1, a[l+1]);
    solve(tr[ro][1], a[r-1], r-1);
    pushup(ro);
}
void build(int ro, int l, int r)
{
    if('1'<=s[l] && s[l]<='9') {
        dp1[ro][0] = dp2[ro][0] = s[l]-'0';
        return ;
    }
    tr[ro][0]=++tot, tr[ro][1]=++tot;
    build(tr[ro][0], l+1, a[l+1]);
    build(tr[ro][1], a[r-1], r-1);
    cnt[ro] = min(mn, cnt[tr[ro][0]]+cnt[tr[ro][1]]+1);
}
void Init() {
    rep(i,0,M-1) rep(j,0,104)
        dp1[i][j]=-1e18, dp2[i][j]=1e18;
    mes(cnt, 0);
    tot = 1;
}
int main()
{
    Init();
    scanf("%s", s+1);
    int len = strlen(s+1);
    scanf("%d%d", &n, &m);
    mn = min(n, m);
    if(n < m) flag = true;  //  false -----
    rep(i,1,len)
    {
        if(s[i]=='(') {
            Stack.push(i);
        }
        else if(s[i]==')') {
            int u = Stack.top(); Stack.pop();
            a[u] = i, a[i] = u;
        }
        else if('1'<=s[i] && s[i]<='9') {
            a[i] = i;
        }
    }
    build(1, 1, len);
    solve(1, 1, len);
    printf("%lld
", dp1[1][mn]);

    return 0;
}