【思路】

01 背包变式，反向递推求最优方案。

【代码】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e2 + 5;
int n, m, s[N], w[N], l[N], f[N][N];
signed main() {
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>s[i]>>w[i]>>l[i];
    for(int i = n; i >= 1; i--) 
        for(int j = 1; j <= m; j++) {
            if(j >= s[i]) f[i][j] = max(f[i + 1][j] + l[i], f[i + 1][j - s[i]] + w[i]);
            else f[i][j] = f[i + 1][j] + l[i];
        }
    cout<<f[1][m]<<endl;
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= m; j++) cout<<f[i][j]<<"\t";
    //     cout<<endl;
    // }
    vector<int> v;
    for(int i = 1, j = m; i <= n; i++) {
        if(j >= s[i] && f[i + 1][j] + l[i] <= f[i + 1][j - s[i]] + w[i]) j -= s[i], v.push_back(i);
        // cout<<i<<", "<<j<<endl;
    }
    cout<<v.size()<<endl;
    for(int i : v) cout<<i<<" ";
}

---

【描述】

小明在玩一款打怪升级的游戏，游戏中共有 $n$ 个怪兽，每个对战一次。游戏开始时，小明共有 $m$ 个能量石。每次打一个怪，小明可以选择使用 $s_i$ 个能量石，战胜对手；或者不使用能量石，则必定败给对手。游戏的设置，战胜第 $i$ 个对手获得 $w_i$ 经验，败给第 $i$ 个对手获得 $l_i$ 经验。

请帮小明计算和 $n$ 个怪兽对战结束后，最多获得多少经验，并给出战胜哪些对手的一种方案。如果有多种可行方案，则输出字典序最小的方案，例如，战胜编号 $[2,~3,~5]$ 的对手的经验值和战胜 $[2,~4,~5]$ 的经验值相同，则 $[2,~3,~5]$ 的字典序更小。

【输入】

第一行包含两个整数 $n,~m$（其中 $1\le n,~m\le500$）分别表示怪兽个数和能量石数目。

接下去 $n$ 行，每行三个整数 $s_i,~w_i,~l_i$ 表示第 $i$ 个怪兽的情报，即如果使用 $s_i$ 个能量石，则获得 $w_i$ 经验值，如果不使用能量石，则获得 $l_i$ 经验值（其中 $1\le s_i\le500,~1\le l_i\le wi\le105$)。

【输出】

第一行输出一个整数，表示最多获得的经验值。

第二行输出一个整数 $k$，表示最优方案中需战胜几个怪兽。

第三行输出 $k$ 个整数，从小到大输出战胜的怪兽的编号，如果有多解，则输出编号字典序最小的一组。

【样例】

样例输入1
5 17
6 10 1
5 10 1
4 10 1
5 12 2
12 20 3

样例输入2
5 10
3 7 1
5 10 1
3 20 14
5 1000 991
3 92 86

样例输出1
36
3
1 2 4

样例输出2
1111
3
1 3 5