[POJ3162]Walking Race（DP + 单调队列）

传送门

题意：一棵n个节点的树。wc爱跑步，跑n天，第i天从第i个节点开始跑步，每次跑到距第i个节点最远的那个节点（产生了n个距离），现在要在这n个距离里取连续的若干天，使得这些天里最大距离和最小距离的差小于M，问怎么取使得天数最多？

求每个点到最远距离的点的距离可以用 cputer 的方法。

至于第二问，可以跑一遍2个单调队列。

具体是固定左端点，右端点向右平移到最远，直到不能平移，再左端点向右平移一位。在这中间维护单调队列和更新 ans 最大值。

具体细节看代码

——代码

#include <cstdio> #include <cstring> #include <iostream> #define N 1000001 #define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, cnt, h1 = 1, t1, h2 = 1, t2, ans; int head[N], to[N << 1], val[N << 1], next[N << 1], f[N][3], a[N], q1[N], q2[N]; bool vis[N]; inline int read() inline void add(int x, int y, int z) inline void dfs1(int u) } f[u][0] = d1; f[u][1] = d2; } inline void dfs2(int u) } } int main() memset(vis, 0, sizeof(vis)); dfs1(1); memset(vis, 0, sizeof(vis)); dfs2(1); for(i = 1; i <= n; i++) a[i] = max(f[i][0], f[i][2]); for(x = 1, y = 0; x <= n; x++) ans = max(ans, y x); } printf("%d\n", ans); } return 0; }

　　

上一篇：[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）

下一篇：[luoguP2045] 方格取数加强版（最小费用最大流）

---

DP 单调队列