G-rated

What are you waiting for?

0%

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;
}