精卫填海

https://www.luogu.com.cn/problem/P1510

#include <bits/stdc++.h>
using namespace std;
#define int long long
int v, n, c;            // 需求的体积，物品数量，目前有的力气值
int k[10010], m[10010]; // 第i块石头对应的体积和所需的力气
// dp[i]（i!=v）: 恰好总计 i 的体积的石头最少需要的力气值
// dp[v]：总计大于等于 i 的体积的石头最少需要的力气值
int dp[10010];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> v >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> k[i] >> m[i];
    }
    memset(dp, 0x3f, sizeof(dp)); // 0x3f3f3f3f 表示无法达成
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = v; j >= 0; j--)
        {
            // dp[j + k[i]] = min(dp[j + k[i]], dp[j] + m[i]);
            int jj = min(v, j + k[i]); // j+k[i] 超过 v 的都认为达成的体积是 v
            dp[jj] = min(dp[jj], dp[j] + m[i]);
        }
    }
    if (dp[v] <= c)
        cout << c - dp[v];
    else
        cout << "Impossible";
    return 0;
}