精卫填海

梁梦露大约 3 分钟教学文档动态规划

精卫填海

1. 题目描述：

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？事实上，东海未填平的区域还需要至少体积为 v 的木石才可以填平，而西山上的木石还剩下 n 块，每块的体积和把它衔到东海需要的体力分别为 k 和 m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为 c。

输入格式：

输入文件的第一行是三个整数：v, n, c。
从第二行到第 n+1 行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式:

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出 Impossible。

输入样例1:

100 2 10 50 5 50 5

输出样例1:

输入样例2:

10 2 1 50 5 10 2

输出样例2:

Impossible

2. 题目解析：

定义状态
我们可以定义一个二维的状态数组 dp[i][j]，其中：

i 表示考虑前 i 块木石（i 的取值范围是从 0 到 n，n 为木石的总数量）；
j 表示消耗的体力值（j 的取值范围是从 0 到 c，c 为精卫初始剩余的体力）。

dp[i][j] 的值表示在前 i 块木石中，消耗 j 个体力所能获得的最大木石总体积。

状态转移方程
对于 dp[i][j]，我们分两种情况来考虑如何从前面的状态转移过来：

不选择第 i 块木石：dp[i][j] = dp[i - 1][j]（当 j < m[i - 1] 时）。
选择第 i 块木石：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - m[i - 1]] + k[i - 1])（当 j >= m[i - 1] 时）。

初始化
当 i = 0 时，dp[0][j] = 0（j 取值从 0 到 c）。
当 j = 0 时，dp[i][0] = 0（i 取值从 0 到 n）。
计算过程
使用动态规划来解决 “精卫填海” 问题，判断是否能填平东海以及计算填平后剩余的最大体力：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int v, n, c;
    cin >> v >> n >> c;
    vector<int> k(n);  // 存储每块木石的体积
    vector<int> m(n);  // 存储每块木石搬运消耗体力

    for (int i = 0; i < n; ++i) {
        cin >> k[i] >> m[i];
    }

    // 创建二维数组dp用于动态规划，dp[i][j]表示考虑前i块木石，消耗j体力时获得的最大木石总体积
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));

    // 填充dp数组，按照状态转移方程进行状态转移
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= c; ++j) {
            if (j < m[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - m[i - 1]] + k[i - 1]);
            }
        }
    }

    bool found = false;
    // 判断是否能填平东海并输出结果
    for (int j = 0; j <= c; ++j) {
        if (dp[n][j] >= v) {
            cout << c - j << endl;
            found = true;
            break;
        }
    }

    if (!found) {
        cout << "Impossible" << endl;
    }

    return 0;
}

判断结果与输出
最后，我们需要遍历 dp[n][j]（j 从 0 到 c），看是否存在某个 j，使得 dp[n][j] >= v。如果存在这样的 j，那么精卫能填平东海，且填平后剩下的最大体力就是 c - j。如果遍历完都没有找到满足 dp[n][j] >= v 的 j，则说明精卫无法填平东海，输出 Impossible。