[GDOI2014] 采集资源

GitHub跳转原题关系图返回列表

先用完全背包预处理“花费 x 资源当秒最多新增多少采集效率”，再按时间推进 DP：dp[j] 表示当前手里有 j 资源时的最大已有采集效率。

OJ: luogu

题目 ID: P3891

难度:提高+/省选-

标签:动态规划完全背包状态设计分类讨论

日期: 2026-06-21 09:44

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

开始时你有 M 点资源，目标是在最短时间内让资源数量达到至少 T。

有 N 种苦工可以无限建造。
第 i 种苦工：

  • 建造花费 A_i 点资源
  • 建成后每秒能采集 B_i 点资源

一秒内的流程是：

  1. 先用当前手头资源建造任意多个苦工
  2. 这些新苦工会立刻在这一秒参与采集
  3. 这一秒结束时获得所有已有苦工的总采集量

求最少多少秒能使资源达到至少 T。

思路

先看一个可以直接验证想法的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int MAXT = 25;

int n, m, target;
int a[MAXN];
int b[MAXN];
vector<pair<int, int>> plans;

void dfs_plan(int idx, int used, int gain) {
    if (used > target) {
        return;
    }
    if (idx > n) {
        plans.push_back(make_pair(used, gain));
        return;
    }

    int limit = target / max(1, a[idx]);
    for (int cnt = 0; cnt <= limit; cnt++) {
        long long next_used = 1LL * used + 1LL * cnt * a[idx];
        long long next_gain = 1LL * gain + 1LL * cnt * b[idx];
        if (next_used > target || next_gain > 1000000) {
            break;
        }
        dfs_plan(idx + 1, (int) next_used, (int) next_gain);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 先枚举“一秒内可能建造出的所有苦工组合”，
    // 再按天做宽搜，状态是（当前资源，已有采集效率）。
    cin >> n >> m >> target;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }

    if (m >= target) {
        cout << 0 << '\n';
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] == 0 && b[i] > 0) {
            cout << 1 << '\n';
            return 0;
        }
    }

    dfs_plan(1, 0, 0);
    sort(plans.begin(), plans.end());
    plans.erase(unique(plans.begin(), plans.end()), plans.end());

    vector<vector<int>> vis(target, vector<int>(target + 1, 0));
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(m, 0, 0));
    vis[m][0] = 1;

    while (!q.empty()) {
        int res = get<0>(q.front());
        int prod = get<1>(q.front());
        int day = get<2>(q.front());
        q.pop();

        for (size_t i = 0; i < plans.size(); i++) {
            int cost = plans[i].first;
            int add = plans[i].second;
            if (cost > res) {
                continue;
            }

            int next_prod = prod + add;
            if (next_prod > target) {
                next_prod = target;
            }

            long long next_res = 1LL * res - cost + prod + add;
            if (next_res >= target) {
                cout << day + 1 << '\n';
                return 0;
            }

            if (!vis[next_res][next_prod]) {
                vis[next_res][next_prod] = 1;
                q.push(make_tuple((int) next_res, next_prod, day + 1));
            }
        }
    }

    return 0;
}

这题最关键的是把“一秒里建哪些苦工”先单独抽出来看。

如果这一秒我们决定花费 x 点资源来造苦工，那么由于每种苦工都可以造任意多个，这其实就是一个完全背包：

gain[x] = 花费 x 资源时，这一秒最多能新增多少采集效率

这个 gain[x] 和具体是哪一天无关，可以先一次性预处理出来。

然后再做按时间推进的 DP。

设：

dp[j] = 当前手里有 j 点资源时，最大已有采集效率

如果当前资源是 j，已有采集效率是 p，这一秒决定花费 x 资源建造苦工，那么：

  • 新增采集效率：gain[x]
  • 下一秒开始前的总采集效率：p + gain[x]
  • 这一秒结束后的资源数：j - x + p + gain[x]

于是就有转移：

next_res = j - x + p + gain[x]

next_prod = p + gain[x]

只要 next_res >= T，当前秒数加一就是答案。

为什么 dp[j] 只保留“最大采集效率”就够了？
因为在同样资源 j 下，采集效率越大，之后每一秒得到的资源只会更多，不会更差。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXT = 1005;
const long long NEG_INF = -(1LL << 60);

int n, m, target;
int a[MAXN];
long long b[MAXN];
long long gain[MAXT]; // gain[c] 表示花费 c 资源，当秒最多新增多少采集效率
long long dp[MAXT], ndp[MAXT];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> target;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }

    if (m >= target) {
        cout << 0 << '\n';
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] == 0 && b[i] > 0) {
            // 0 代价且正收益的单位可以无限造，1 秒内必达目标。
            cout << 1 << '\n';
            return 0;
        }
    }

    for (int i = 0; i <= target; i++) {
        gain[i] = NEG_INF;
    }
    gain[0] = 0;

    // 完全背包：预处理“花费 c 资源最多能新增多少采集效率”。
    for (int i = 1; i <= n; i++) {
        if (a[i] <= 0 || a[i] > target || b[i] <= 0) {
            continue;
        }
        for (int cost = a[i]; cost <= target; cost++) {
            if (gain[cost - a[i]] == NEG_INF) {
                continue;
            }
            gain[cost] = max(gain[cost], gain[cost - a[i]] + b[i]);
        }
    }

    for (int i = 0; i < target; i++) {
        dp[i] = NEG_INF;
    }
    dp[m] = 0; // 第 0 秒结束时，手里有 m 资源，已有采集效率为 0

    for (int day = 0; day <= target; day++) {
        for (int i = 0; i < target; i++) {
            ndp[i] = NEG_INF;
        }

        for (int res = 0; res < target; res++) {
            if (dp[res] == NEG_INF) {
                continue;
            }

            long long prod = dp[res];

            for (int cost = 0; cost <= res; cost++) {
                if (gain[cost] == NEG_INF) {
                    continue;
                }

                long long add = gain[cost];
                long long next_prod = prod + add;
                if (next_prod > target) {
                    next_prod = target;
                }

                long long next_res = 1LL * res - cost + prod + add;
                if (next_res >= target) {
                    cout << day + 1 << '\n';
                    return 0;
                }

                if (next_prod > ndp[next_res]) {
                    ndp[next_res] = next_prod;
                }
            }
        }

        for (int i = 0; i < target; i++) {
            dp[i] = ndp[i];
        }
    }

    return 0;
}

复杂度

设目标资源是 T。

  • 预处理完全背包复杂度 O(NT)O(NT)
  • 按天推进的 DP 复杂度最坏 O(T3)O(T^3)

但这里 T <= 1000，而且一旦到达答案就立刻退出，可以通过。

总结

这题有两层决策：

  1. 一秒内怎么花资源造苦工
  2. 过了若干秒以后，资源和采集效率会变成什么

第一层可以先用完全背包压成 gain[x]，第二层再做时间 DP，整个模型就顺了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析