Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

参照1635的递归方式YY的一个算法。

Posted by Liuzhaoliang at 2014-09-05 11:49:59 on Problem 3437
const int N = 20010;
char s[N];
int h1,h2;
int len;
inline void before(){
    int d = 0;
    for(int i=0;i<len;i++){
        if(s[i]=='d') d++;
        else d--;
        h1=max(d,h1);
    }
}
int dfs(int i,int d){//return number of token eaten
    int st = i;
    //printf("(%d,%d)\n",i,d);
    h2 = max(h2,d);
    while(i<len && s[i]=='d') {//a subtree
        i+=dfs(i+1,++d);
    }
    //printf("tree size %d\n",i-st);
    return i-st+2;
}

int main()
{
    int t=0;
    while(scanf("%s",s),s[0]!='#'){
        h1 = h2 = 0;
        len = strlen(s);
        before();
        dfs(0,0);
        printf("Tree %d: %d => %d\n",++t,h1,h2);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator