题解 | 遗迹探险家小红

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> bz;
vector<bool> visited;
int dp[110][5010][110];
int dfs(int id, int T, int m){
    if(T <= 0 || id >= bz.size())
        return 0;
    //选
    int r1 = 0;
    if(bz[id].first > 30 && m > 0 && T >= bz[id].first){
        if(dp[id + 1][T - bz[id].first][m - 1] == - 1)
           dp[id + 1][T - bz[id].first][m - 1] = dfs(id + 1, T - bz[id].first, m - 1); 
        r1 =  dp[id + 1][T - bz[id].first][m - 1] + bz[id].second;
    }else if(bz[id].first <= 30 && T >= bz[id].first){
        if(dp[id + 1][T - bz[id].first][m] == -1)
            dp[id + 1][T - bz[id].first][m] = dfs(id + 1, T - bz[id].first, m);
        r1 =  dp[id + 1][T - bz[id].first][m] + bz[id].second;
    }
    //不选
    if(dp[id + 1][T][m] == -1)
        dp[id + 1][T][m] = dfs(id + 1, T, m);
    int r2 = dp[id + 1][T][m];
    return max(r1, r2);
}
int main() {
    int n, T, m;
    cin>>n>>T>>m;
    for(int i = 0; i < n + 5; ++i)
        for(int j = 0; j < T + 5; ++j)
            for(int k = 0; k < m + 5; ++k)
                dp[i][j][k] = -1;
    for(int i = 0; i < n; ++i){
        pair<int, int> temp;
        cin>>temp.first>>temp.second;
        bz.push_back(temp);
        visited.push_back(false);
    }
    cout<<dfs(0, T, m);
}
// 64 位输出请用 printf("%lld")