U314392 distjr_想买书 题解

思路

首先是一个 dp 的板子，设 $dp_j$ 为花费 $j$ 元能获得的最大的期待值。

对于每次转移，都可以选择买哪一本书，一旦买了一本书，花费的钱增加 $p_i$ ，获得的总期待值增加 $v_i$ 。

故不难看出状态转移方程为 $dpj = max \lbrace dp{j-p_i}+v_i \rbrace $。

但题目还要求输出方案，所以开一个 vector 记录方案，每次找到更优的方案时，就在上一个方案的后面补上当前新增加的物品，由于输入是单调的，自然保证输出是单调的。

同时，还要设置一个标记数组 flag 以筛去不合法的答案，确保所有找到的方案都是正常计算得来的，否则可能会出现一些奇奇怪怪的bug。

感谢 linmou 提供的 std！

std

/**
 * @file buy.cpp
 * @brief Solution of Luogu U314392
 * @date 2024-02-18
 */
#include <cstdio>
#include <vector>
#define MAXN 505
#define MAXM 500005
using namespace std;

int n, m, a, maxx = 0, v[MAXM], p[MAXM], dp[MAXM], ans;
bool flag[MAXN][MAXM];
vector<int> programme;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d", &a, &p[i], &v[i]);
    flag[n + 1][0] = 1;
    for (int i = n; i >= 1; i--)
    {
        for (int j = 0; j <= m; j++)
            flag[i][j] = flag[i + 1][j];
        for (int j = m; j >= p[i]; j--)
        {
            if (!flag[i + 1][j - p[i]])
                continue;
            if (dp[j] <= v[i] + dp[j - p[i]]) // 状态转移
            {
                dp[j] = v[i] + dp[j - p[i]];
                flag[i][j] = flag[i][j] | flag[i + 1][j - p[i]]; // 标记
            }
        }
    }
    for (int i = 1; i <= m; i++) // 选出最优方案
        if (maxx <= dp[i])
            maxx = dp[i], ans = i;
    int i = 1, j = ans, sum = 0;
    while (i <= n && j)
    {
        if (flag[i][j] && flag[i][j - p[i]])
        {
            printf("%d ", i);
            sum += p[i];
            j -= p[i];
        }
        i++;
    }
    return 0;
}