神仙題マクロ定義シミュレーション、再帰

タイトル説明

神仙題解

yzy神仙の精巧な説明に感謝します.
タイトルの説明

c++      max  .c++     max    .
#define MAX(a,b) (a)>(b)?(a):(b)
                       .
     MAX(2+3,4)      (2+3)>(4)?(2+3):(4),                 .
         ,   MAX()      ,        ,            .
  : MAX(1+1+1,2)+MAX(2,3) 
  : 6 5
  :      3,    3,    6.
        (1+1+1)>(2)?(1+1+1):(2),      4   ,      3     5   .

神仙問題
最初は何の見当もつかなかったが、シミュレーションの問題だと知っていたが、どこから手をつけたのか分からなかった.結局yzy神仙は再帰秒を書いてこの問題を分析した.ここで彼の解法を話します.

/*
  [l,r]  .         ,       .
                          ,                .
        ,          +1.
    ,           MAX     .
        MAX        ,      ,          .
      ,               .
       ,      .
*/
#include //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=2e5;
char c[yuzu|10];
#define ans first
#define add second
typedef pair<int,int> node;
/*first      ,second        .*/
int makenum(int l,int r){//l,r         .
int x=0,i;
for (i=l;i<=r;++i) x=x*10+c[i]-'0';
return x;
}

node work(int l,int r){//    pair
int i,le;//le           .
for (i=l;i<=r;++i) if (!isdigit(c[i])) break;
if (i>r) return node(makenum(l,r),0);//      ,       .
for (i=l,le=0;i<=r;++i){//           .
  if (c[i]=='(') le++;
  if (c[i]==')') le--;
  if (!le&&c[i]=='+') break;//le 0              .
  }
if (i<=r){//     
  node a=work(l,i-1),b=work(i+1,r);//      .
  return node(a.ans+b.ans,a.add+b.add+1);//    ,        +1.
  }
for (i=l+4,le=0;i<=r;++i){// l+4        "MAX("    .
  if (c[i]=='(') le++;
  if (c[i]==')') le--;
  if (!le&&c[i]==',') break;//      ','
  }
node a=work(l+4,i-1),b=work(i+1,r-1);//        .
return a.ans>b.ans?node(a.ans,a.add*2+b.add):node(b.ans,b.add*2+a.add);
/*ans       ,add        +    .*/
}

int main(){
scanf("%s",c+1);
int n=strlen(c+1);
node llx=work(1,n);
printf("%d %d",llx.ans,llx.add);//    .
}

ありがとうございます.