比赛 20160407树结构练习 评测结果 AAAAA
题目名称 最终得分 100
用户昵称 KZNS 运行时间 0.001 s
代码语言 C++ 内存使用 0.31 MiB
提交时间 2016-04-07 20:49:04
显示代码纯文本
//KZNS
#include <fstream>
#include <iostream>
#include <utility>
using namespace std;
//
ifstream fin ("sumtree.in");
ofstream fout ("sumtree.out");
typedef pair<int, int> pr;//v, id;
//
int tg[10003];
int ls[10003];
//
pr mn(int l, int r, int x, int y) {
	if (r < l)
		return make_pair(0x7fffffff, 0x7fffffff);
	if (l == r)
		return make_pair(ls[r], ls[r]);
	pr a = mn(l, r-(y-tg[ls[r]])-1, x, tg[ls[r]]-1);
	pr b = mn(r-(y-tg[ls[r]]), r-1, tg[ls[r]]+1, y);
	if (a.first < b.first) {
		a.first += ls[r];
		return a;
	}
	else if (a. first > b.first) {
		b.first += ls[r];
		return b;
	}
	else {
		if (a.second < b.second) {
			a.first += ls[r];
			return a;
		}
		else {
			b.first += ls[r];
			return b;
		}
	}
}
//
int main() {
	int a;
	int len;
	while (fin >> a) {
		tg[a] = 0;
		for (len = 1; fin.peek()!='\r'&&fin.peek()!='\n'; len++) {
			fin >> a;
			tg[a] = len;
		}
		fin >> ls[0];
		for (int i = 1; fin.peek()!='\r'&&fin.peek()!='\n'; i++)
			fin >> ls[i];
		fout << mn(0, len-1, 0, len-1).second << endl;
	}
	return 0;
}
//UBWH