2023 种树 · 方案一按深度贪心

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1670 字

n 个点的树，种花在第 i 个点第 t 天有收益 a_i +

2023
贪心

正文

// CSP-S 2023 复赛 T4 · 种树（方案一：按深度贪心暴力，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2023D
// 题意：n 个点的树，种花在第 i 个点第 t 天有收益 a_i + t·b_i（b 可负）。
//       必须先种父亲才能种儿子。每天恰好种一棵，n 天种完。求最大
//       总收益（n ≤ 1e5，小数据部分分 n ≤ 500）。
// 思路（直观贪心）：
//   收益随时间变化（b_i 正的越早种越好，b_i 负的越晚种越好）。
//   暴力：每天从"父已种的可种点"里选当前最优（按 a_i + t·b_i 最大），
//   O(n^2)：n ≤ 500 的部分分（测试点 1~4、5~6 部分可过）。
//   注意贪心在一般树上不是最优（交换论证有反例），但作为部分分
//   与理解题意的基准足够。
// 复杂度：O(n^2)。
// 易错点：
//   1. t 从 0 还是 1 计（按题面第一天 t=0）；
//   2. b_i 可为负：负 b 的点留到后期，但受父亲约束；
//   3. 根必须第一天种（它没父亲）——不一定，若根 b 大可后种？
//      根无父亲随时可种，按贪心自然处理。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n;
long long a[1005], b[1005];
vector<int> g[1005];
bool planted[1005];
bool ready[1005];                      // 父已种（或为根）

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ready[1] = true;                   // 根随时可种
    long long ans = 0;
    for (int t = 0; t < n; t++) {
        int best = 0;
        long long bestV = -4e18;
        for (int u = 1; u <= n; u++) {
            if (!ready[u] || planted[u]) continue;
            long long v = a[u] + (long long)t * b[u];
            if (v > bestV) {
                bestV = v;
                best = u;
            }
        }
        planted[best] = true;
        ans += bestV;
        for (int v : g[best])
            if (!planted[v]) ready[v] = true;
    }
    printf("%lld\n", ans);
    return 0;
}

2023 种树 · 方案一 按深度贪心

正文

CSP-S 标程 · 复赛真题的其它内容

2023 种树 · 方案一按深度贪心