比赛 |
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