大家好，我是энтджей，今天是我2026年第十次正式发题解！

2026年发布的题解！

能不能点个赞

类似题目传送门

相同题目传送门

类似题目传送门

---

首先简化题意：

• 大致就是先告诉你容量，然后告诉你占据容积、获得的价值、购买次数，然后做背包问题

然后就是写代码

• 处理输入（read）：

  • 正常输入

• 核心部分（process）：

  • 可以把可以无限参观的看做完全背包，把其他的看做多重01背包
  • 然后按公式计算
    • 即：
      • $dp[j] = max(dp[j], dp[j - t[i]] + c[i])$

• 最后输入最大时间（write）：

  • 输出dp的第容量项

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1e4 + 10;
int CanUseTime;     // 还有多久上学
int n,m;              // 樱花棵树
int t[N],c[N],p[N]; // 记录 耗费的时间 美学值 可参观次数
int dp[N];          // 背包问题（优化后）dp数组
void read(){ //输入
    cin >> m >> n;
    for(int i = 1;i <= n; i++){
        cin >> t[i] >> c[i] >> p[i]; //输入Ti Ci Pi
    }
}

void process(){ //处理
    for(int i = 1; i <= n; i++) {
        if(p[i] == 0) { //无限次观看 —— 完全背包
            for(int j = t[i]; j <= m; j++) {
                dp[j] = max(dp[j], dp[j - t[i]] + c[i]);     //dp状态转移
            }
        } else {        //有限次参观 —— 01背包
            for(int step = 1; step <= p[i]; step++){
                for(int j = m; j >= t[i]; j--){
                    dp[j] = max(dp[j], dp[j - t[i]] + c[i]); //dp状态转移
                }
            }
        }
    }
}

void write(){ //输出
    cout << dp[m];
}

signed main(){
    ios::sync_with_stdio(false); //加速输入输出
    cin.tie(0),cout.tie(0);      //进一步加速

    //全过程：
    read();
    process();
    write();
    
    return 0;
}

---

🎉完结撒花🎉