题解 | 遗迹探险家小红

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

struct Treasure{
    int t,price;
    bool isHeavy;
};

int main() {
    int n,T,M;
    cin>>n>>T>>M;
    vector<Treasure> treasure(n);
    
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        treasure[i]={a,b,a>30};
    }
    
    // dp[j][k]：时间不超过j，且使用了恰好k个重型宝藏时的最大价值
    vector<vector<int>> dp(T+1,vector<int>( M+1,0 ));
   
    for(const auto& item : treasure){
        int t=item.t;
        int p=item.price;
        bool heavy=item.isHeavy;

        for(int j=T;j>=t;j--){
            if(!heavy){
                // 情况1：普通宝藏，不占用重型配额
                // 它可以从任意重型数量k的状态转移过来
                for(int k=0;k<=M;k++){
                    dp[j][k]=max(dp[j][k],dp[j-t][k]+p);
                }
            }else{
                // 情况2：重型宝藏，必须占用一个重型配额 (k从1开始)
                for(int k=1;k<=M;k++){
                    dp[j][k]=max(dp[j][k],dp[j-t][k-1]+p);
                }
            }
        }
    }

    int maxp=0;
    for(int j=0;j<=T;j++){
        for(int k=0;k<=M;k++){
            maxp=max(maxp,dp[j][k]);
        }
    }

    cout<<maxp<<endl;
    return 0;

}