POJ 1661 Help Jimmy——树形dp

POJ 1661 Help Jimmy——树形dp

把端点看做节点，把时间看做边的权值建立状态转移树，然后记忆化搜索一遍即可，建树过程很麻烦，权当是个模拟题了、、、

#include #include #include #include #include #include

G[maxn];map m;int dfs(int u) { if (dp[u] != -1) return dp[u]; if (u == tail) return dp[u] = 0; int temp = INF; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].first, val = G[u][i].second; temp = min(temp, dfs(v) + val); } return dp[u] = temp;}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d %d %d", &N, &X, &Y, &MAX); for (int i = 1; i <= (N<<1) + 10; i++) { G[i].clear(); dp[i] = -1; } m.clear(); int cnt = 0; P p = make_pair(X, Y); m[p] = ++cnt; for (int i = 1; i <= N; i++) { scanf("%d %d %d", &plant[i].x, &plant[i].y, &plant[i].h); P p1 = make_pair(plant[i].x, plant[i].h), p2 = make_pair(plant[i].y, plant[i].h); if (!m[p1]) m[p1] = ++cnt; if (!m[p2]) m[p2] = ++cnt; plant[i].id1 = m[p1], plant[i].id2 = m[p2]; } sort(plant + 1, plant + 1 + N); tail = ++cnt; bool ok = false; for (int i = 1; i <= N; i++) { int x = plant[i].x, y = plant[i].y, h = plant[i].h, id1 = plant[i].id1, id2 = plant[i].id2; if (MAX < Y - h) break; if (x <= X && X <= y) { ok = true; G[1].push_back(make_pair(id1, X - x + Y - h)); G[1].push_back(make_pair(id2, y - X + Y - h)); break; } } if (!ok && MAX >= Y) G[1].push_back(make_pair(tail, Y)); for (int i = 1; i <= N; i++) { bool ok1 = false, ok2 = false; int x = plant[i].x, y = plant[i].y, h = plant[i].h, id1 = plant[i].id1, id2 = plant[i].id2; for (int j = i + 1; j <= N; j++) { int xx = plant[j].x, yy = plant[j].y, hh = plant[j].h, id11 = plant[j].id1, id22 = plant[j].id2; if (MAX < h - hh) break; if (!ok1 && xx <= x && x <= yy) { ok1 = true; G[id1].push_back(make_pair(id11, x - xx + h - hh)); G[id1].push_back(make_pair(id22, yy - x + h - hh)); } if (!ok2 && xx <= y && y <= yy) { ok2 = true; G[id2].push_back(make_pair(id11, y - xx + h - hh)); G[id2].push_back(make_pair(id22, yy - y + h - hh)); } if (ok1 && ok2) break; } if (!ok1 && MAX >= h) G[id1].push_back(make_pair(tail, h)); if (!ok2 && MAX >= h) G[id2].push_back(make_pair(tail, h)); } printf("%d\n", dfs(1)); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。