Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
参照1635的递归方式YY的一个算法。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator