迷宫寻宝
发布时间
阅读量：
阅读量
描述 Description：
由单一入口通向多个出口的树状迷宫内部隐藏了丰富的宝藏，在每个路口都蕴藏着特定数量的宝藏。该迷宫设计为单向流程，只能从入口出发前往各个分支路口，并无回头路。为了获取尽可能多的宝藏，请你规划路径从入口进入迷宫，并在合适的位置选取出口。
输入格式 Input Format：
第一行：交叉口的数量为n（其中n < 1, 245）。
第二行：具体数值对应着所有交叉口，并按照其编号排列。
除此之外还有n-1组数据：每一组包含两个数值i和j，代表某条道路的起始点为i而结束于j，并且这些数据满足条件i < j。
输出格式 Output Format：
一行：从入口到某一出口所能获得的最大宝藏数量。
输入样例：
9
10 20 15 25 30 40 5 20 4
1 2
1 3
1 4
2 5
2 6
3 7
3 8
7 9
输出样例：
70
思路：
根据题目把树随便建出来，dp。（本题卡常）
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define loop( i, a, b ) for( long long i = a; i <= b; i++ )
#define maxn 100010
using namespace std;
struct haha {
long long num, dad;
}f[maxn];
long long v[maxn], dp[maxn];
long long n;
void haha_tree() {
long long a, b;
scanf( "%lld", &n );
loop( i, 1, n )
scanf( "%lld", &v[i] );
loop( i, 1, n - 1 ) {
scanf( "%lld%lld", &a, &b );
f[b].dad = a;
f[b].num = i;
}
}
int main() {
haha_tree();
loop( i, 1, n ) {
dp[i] = dp[f[i].dad] + v[i];
}
long long ans;
loop( i, 1, n )
ans = max( ans, dp[i] );
printf( "%lld", ans );
return 0;
}
代码解读全部评论 (0)
还没有任何评论哟~