cf935E

题解：

树形dp

要记录一个最小的，一个最大的

然后转移

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int p,m,g[N*][],f[N*][],T[N*][],size[N*],num;

char s[N*];

int build(int x,int y)

{

    if (x==y)

     {

         num++;

         f[num][]=g[num][]=s[x]-'';

         return num;

     }

    int l=;

    for (int i=x;i<=y;i++)

     {

         if (s[i]=='(')l++;

         if (s[i]==')')l--;

         if (s[i]=='?'&&l==)

          {

             int l=build(x+,i-),r=build(i+,y-);

             num++;

             T[num][]=l;T[num][]=r;

             size[num]=size[l]+size[r]+;

            return num;

          }

     }

}

void dfs(int x)

{

    if (!T[x][]&&!T[x][])return;

    dfs(T[x][]);dfs(T[x][]);

    int l=T[x][],r=T[x][];

    if (p<m)

     {

         for (int i=;i<=p;i++)

          for (int j=;j<=i;j++)

           if (j<=size[l]&&i-j<=size[r])

            g[x][i]=min(g[x][i],g[l][j]-f[r][i-j]);

         for (int i=;i<=p;i++)

          for (int j=;j<i;j++)

           if (j<=size[l]&&i-j-<=size[r])

            g[x][i]=min(g[x][i],g[l][j]+g[r][i-j-]);

         for (int i=;i<=p;i++)

          for (int j=;j<=i;j++)

           if (j<=size[l]&&i-j<=size[r])

            f[x][i]=max(f[x][i],f[l][j]-g[r][i-j]);

         for (int i=;i<=p;i++)

          for (int j=;j<i;j++)

           if (j<=size[l]&&i-j-<=size[r])

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

     }

    else

     {

         for (int i=;i<=m;i++)

          for (int j=;j<=i;j++)

           if (j<=size[l]&&i-j<=size[r])

            g[x][i]=min(g[x][i],g[l][j]+g[r][i-j]);

         for (int i=;i<=m;i++)

          for (int j=;j<i;j++)

           if (j<=size[l]&&i-j-<=size[r])

            g[x][i]=min(g[x][i],g[l][j]-f[r][i-j-]);

         for (int i=;i<=m;i++)

          for (int j=;j<=i;j++)

           if (j<=size[l]&&i-j<=size[r])

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

         for (int i=;i<=m;i++)

          for (int j=;j<i;j++)

           if (j<=size[l]&&i-j-<=size[r])

            f[x][i]=max(f[x][i],f[l][j]-g[r][i-j-]);

     }

}

int main()

{

    scanf("%s",&s);

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

    memset(f,0x8f,sizeof f);

    memset(g,0x3f,sizeof g);

    int root=build(,strlen(s)-);

    dfs(root);

    printf("%d",f[root][min(p,m)]);

}