牛客周赛

二维写法

typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 310;
const int M = 2e5 + 10;
const int mod  = 998244353;
ll a[N],p[N],c[N],u[N],l[N];
ll dp[N][N];    //代表前i个物品，金币为j的最大战力
void solve() {
    ll n,x;
    cin>>n>>x;
    for(int i = 1 ; i <= n ; i++){
        cin>>a[i]>>p[i]>>c[i]>>u[i]>>l[i];
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n ; i++){
        for(int j = 0 ; j <= x ; j++){
            dp[i][j] = dp[i - 1][j];
        }
        for(int j = 0; j <= x; j++){
            for(int k = 0 ; k <= l[i] && k * c[i] <= j - p[i] ; k++){    //k为0时，就代表没升级
                dp[i][j] = max(dp[i][j], dp[ i - 1 ][ j - p[i] - k*c[i] ] + a[i] + k*u[i]);
            }
        }
    }
    cout<<dp[n][x]<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}

一维写法

typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 310;
const int M = 2e5 + 10;
const int mod  = 998244353;
ll a[N],p[N],c[N],u[N],l[N];
ll dp[N];      //代表金币数为i的最大战力
void solve() {
    ll n,x;
    cin>>n>>x;
    for(int i = 1 ; i <= n ; i++){
        cin>>a[i]>>p[i]>>c[i]>>u[i]>>l[i];
    }
    for(int i = 1 ; i <= n ; i++){
        for(int j = x; j >= p[i]; j--){     //倒序枚举体积
            for(int k = 0; k <= l[i] && k*c[i] <= j - p[i]; k++){
                dp[j] = max(dp[j] , dp[j - p[i] - k * c[i]] + a[i] + k * u[i]);
            }
        }
    }
    cout<<dp[x]<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}