hdu 3660 Alice and Bob's Trip

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:有根树,每条边有权,a和b都在0点,开始往下走,b走的策略是希望路径和尽量大,a希望尽量少。b先走。但是要求最后走出的权值和在[L,R]之内。

这个的话,要dp还是不难想的

dp[u]表示从u点向走能走出的最优策略。

这里的最优策略其实不要去讨论是u的还是v的,因为他们是轮流走的,设0点所在的层数是0,那么点u只是是在偶数层,那么一定是u在走,那么就一定是u能走出的最优策略的,相反在奇数层一定是a能走出的最优策略

另外要记录一个信息,就是从点0走到点u的路径长度,这个一边dfs一边记录即可

转移:

能转移的前提是 L <= len[u] + w + dp[v] <= R,满足这个条件的才能考虑转移

在偶数层,是为了使b走出最大:dp[u] = max(w + dp[v]);

在奇数层,是为了使a走出最小:dp[u] = min(w + dp[v]);

然后转移即可,对于叶子,dp[u] = 0;

这题数据给出就是有根树了,不要建无根树

另外这题时间卡得很紧,这样已经是O(n)复杂度了但是很容易超时,用c++提交吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 500010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,L,R,tot,head[N],dp[N],len[N];
struct edge{
int u,v,w,next;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
}e[N];

bool check(int x){
if(x >= L && x <= R)
return true;
return false;
}

inline void add(int u,int v,int w){
e[tot] = edge(u,v,w);
e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u,int d,bool people){
len[u] = d;
if(len[u] > R){
dp[u] = 0; return ;
}
bool leaf = true;
dp[u] = people ? 0 : INF;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
leaf = false;
dfs(v,d+w,(!people));
if(check(len[u] + w + dp[v])){
if(people) dp[u] = max(dp[u] , w + dp[v]);
else dp[u] = min(dp[u] , w + dp[v]);
}
}
if(leaf) dp[u] = 0;
}

int main(){
while(scanf("%d%d%d",&n,&L,&R)!=EOF){
tot = 0; cl(head,-1);
for(int i = 1; i < n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dfs(0,0,true);
if(!check(dp[0]))
puts("Oh, my god!");
else
printf("%d\n",dp[0]);
}
return 0;
}