P1270 “访问”美术馆

树形dp入门题

1.P1270“访问”美术馆

题目描述

经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。

输入格式

第1行是警察赶到的时间，以s为单位。第2行描述了艺术馆的结构，是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第2个数是它末端的藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出，请看样例。

一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。

输出格式

输出偷到的画的数量

题目分析

按照题目意思建树，观察可得，偷一幅画要进去出来，那么就把边长乘二，然后直接跑树形dp就好了。

代码

//
// Created by mrx on 2022/9/4.
//
#include <bits/stdc++.h>

using ll = long long;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif
    int limit;
    std::cin >> limit;
    std::vector<std::pair<int, int>> s;
    s.emplace_back(0, 0);
    int tot = 0;
    int c, paint;
    while (std::cin >> c >> paint) {
        s.emplace_back(c * 2, paint);
        tot += paint;
    }
    int n = s.size();
    std::vector<std::vector<std::pair<int, int>>> G(n + 1);
    std::vector<int> fa(n + 1);
    std::vector<int> wei(n + 1);
    int cur = 1;
    std::function<void(int)> build = [&](int id) {
        wei[id] = s[id].second;
        if (wei[id] == 0) {
            G[id].emplace_back(cur + 1, s[cur + 1].first);
            build(++cur);//ls
            G[id].emplace_back(cur + 1, s[cur + 1].first);
            build(++cur);//rs
        }
    };
    G[0].emplace_back(1, s[1].first);
    build(1);
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(tot + 1, 0x3f3f3f3f));

    std::function<void(int)> dfs = [&](int u) {
        if (G[u].empty()) {
            for (int i = 0; i <= wei[u]; ++i) {
                dp[u][i] = i * 5;
            }
        }
        dp[u][0] = 0;
        for (auto [v, w]: G[u]) {
            dfs(v);
            wei[u] += wei[v];
            for (int i = std::min(tot, wei[u]); i >= 1; --i) {
                for (int j = std::min(i , wei[v]); j >= 0; --j) {
                    dp[u][i] = std::min(dp[u][i], dp[u][i - j] + dp[v][j] + w);
                }
            }
        }

    };
    dfs(0);
    int ans = 0;
    for (int i = 0; i <= tot; ++i) {
        if (dp[0][i] <limit)ans = i;
    }
    std::cout << ans << '\n';
    return 0;
}