I题题解

具体请看注释喔

这道题和https://ac.nowcoder.com/acm/contest/81126/E 非常像

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

const int N = 5e3 + 10;

int dp[N][N][2];

void solve() {
    int n, m, V;
    std::cin >> n >> m >> V;
    
    std::vector<int> v(n + 1);
    memset(dp, -0x3f, sizeof dp);
    for(int i = 1; i <= n; i++) std::cin >> v[i];

    dp[0][0][0] = dp[0][0][1] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= V; j++) {
            //dp[i][j][0] 代表到第i个物品 装满j空间 未使用过魔法
            //dp[i][j][1] 代表到第i个物品 装满j空间 已使用过魔法
            dp[i][j][0] = dp[i - 1][j][0];
            dp[i][j][1] = dp[i - 1][j][1];
            
            if(j < v[i]) continue;
            
            //未使用过魔法只能从未使用过魔法的状态转移而来
            dp[i][j][0] = std::max(dp[i][j][0], dp[i - 1][j - v[i]][0] + 1);
            
          	//显而易见的结论是 魔法只对某一个物品用完最优
            //已使用过魔法可以从已使用过魔法的状态转移 还可以从未使用过魔法的状态使用m次魔法转移
            dp[i][j][1] = std::max({dp[i][j][1], dp[i - 1][j - v[i]][1] + 1, dp[i - 1][j - v[i]][0] + v[i]*m + 1});

            //std::cout << "dp[" << i << "][" << j << "][0] = " << dp[i][j][0] << '\n';
            //std::cout << "dp[" << i << "][" << j << "][1] = " << dp[i][j][1] << '\n';
        }
    }

    int res = std::max(dp[n][V][0], dp[n][V][1]);
    if(res < 0) std::cout << -1 << '\n';
    else std::cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
     
    int T = 1;;
    //std::cin >> T;
    while (T--) solve();
    return 0;
}