首页 > 代码库 > [POJ3162]Walking Race（DP + 单调队列）
[POJ3162]Walking Race（DP + 单调队列）
传送门
题意：一棵n个节点的树。wc爱跑步，跑n天，第i天从第i个节点开始跑步，每次跑到距第i个节点最远的那个节点（产生了n个距离），现在要在这n个距离里取连续的若干天，使得这些天里最大距离和最小距离的差小于M，问怎么取使得天数最多？
求每个点到最远距离的点的距离可以用 computer 的方法。
至于第二问，可以跑一遍2个单调队列。
具体是固定左端点，右端点向右平移到最远，直到不能平移，再左端点向右平移一位。在这中间维护单调队列和更新 ans 最大值。
具体细节看代码
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 1000001 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 7 int n, m, cnt, h1 = 1, t1, h2 = 1, t2, ans; 8 int head[N], to[N << 1], val[N << 1], next[N << 1], f[N][3], a[N], q1[N], q2[N]; 9 bool vis[N]; 10 11 inline int read() 12 { 13 int x = 0, f = 1; 14 char ch = getchar(); 15 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 16 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 17 return x * f; 18 } 19 20 inline void add(int x, int y, int z) 21 { 22 to[cnt] = y; 23 val[cnt] = z; 24 next[cnt] = head[x]; 25 head[x] = cnt++; 26 } 27 28 inline void dfs1(int u) 29 { 30 int i, v, d1 = 0, d2 = 0; 31 vis[u] = 1; 32 for(i = head[u]; i ^ -1; i = next[i]) 33 { 34 v = to[i]; 35 if(!vis[v]) 36 { 37 dfs1(v); 38 if(f[v][0] + val[i] > d1) d2 = d1, d1 = f[v][0] + val[i]; 39 else if(f[v][0] + val[i] > d2) d2 = f[v][0] + val[i]; 40 } 41 } 42 f[u][0] = d1; 43 f[u][1] = d2; 44 } 45 46 inline void dfs2(int u) 47 { 48 int i, v; 49 vis[u] = 1; 50 for(i = head[u]; i ^ -1; i = next[i]) 51 { 52 v = to[i]; 53 if(!vis[v]) 54 { 55 if(f[v][0] + val[i] == f[u][0]) f[v][2] = f[u][1] + val[i]; 56 else f[v][2] = f[u][0] + val[i]; 57 f[v][2] = max(f[v][2], f[u][2] + val[i]); 58 dfs2(v); 59 } 60 } 61 } 62 63 int main() 64 { 65 int i, x, y, z; 66 while(~scanf("%d %d", &n, &m)) 67 { 68 ans = cnt = 0; 69 memset(f, 0, sizeof(f)); 70 memset(head, -1, sizeof(head)); 71 for(i = 1; i < n; i++) 72 { 73 x = read(); 74 y = read(); 75 add(i + 1, x, y); 76 add(x, i + 1, y); 77 } 78 memset(vis, 0, sizeof(vis)); 79 dfs1(1); 80 memset(vis, 0, sizeof(vis)); 81 dfs2(1); 82 for(i = 1; i <= n; i++) a[i] = max(f[i][0], f[i][2]); 83 for(x = 1, y = 0; x <= n; x++) 84 { 85 while(q1[h1] < x && h1 <= t1) h1++; 86 while(q2[h2] < x && h2 <= t2) h2++; 87 while(a[q1[h1]] - a[q2[h2]] < m && y <= n) 88 { 89 y++; 90 while(a[q1[t1]] < a[y] && h1 <= t1) t1--; 91 q1[++t1] = y; 92 while(a[q2[t2]] > a[y] && h2 <= t2) t2--; 93 q2[++t2] = y; 94 } 95 ans = max(ans, y - x); 96 } 97 printf("%d\n", ans); 98 } 99 return 0;100 }
[POJ3162]Walking Race（DP + 单调队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。