学步园

直接递归得答案：

#include<stdio.h>
#include<stdlib.h>
#define Max 10000

int in[Max] = {0};
int po[Max] = {0};
int leaf = 0,sum = 0x7fffffff;
int e1,e2;

int dfs(int * s1,int * s2,int length,int ans){
	int i = 0;
	if(length){
		while(s2[length-1] != s1[i])i++;
		ans += s2[length-1];
		e1 = dfs(s1,s2,i,ans);
		e2 = dfs(s1+i+1,s2+i,length-i-1,ans);
			if(e1 && e2){
				if(sum >= ans){
					leaf = s2[length-1];
					sum = ans;
				}
			}
			return 0;
	}
	return 1;
}

int main(void){
	int num,i = 0,line = 0,len;
	char ch;
	while(scanf("%d%c",&num,&ch) != EOF){
		if(line == 0){
			in[i++] = num;
		}
		else if(line == 1){
			po[i++] = num;
		}
		if(ch == '\n'){
			line++;
			len = i;
			i = 0;
		}
		if(line == 2){
			sum = 0x7fffffff;
			dfs(in,po,len,0);
			printf("%d\n",leaf);
			line = 0;
		}
	}
	return 0;
}