C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 1272K, 提交时间: 2023-07-25 20:05:17

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
	int a,d,t;
	bool operator<(const node& b) const
	{
		return d*1.0/t>b.d*1.0/b.t;
	}
}n[55];
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int N,T;
	cin>>N>>T;
	for(int i=1;i<=N;i++) cin>>n[i].a;
	for(int i=1;i<=N;i++) cin>>n[i].d;
	for(int i=1;i<=N;i++) cin>>n[i].t;
	sort(n+1,n+1+N);
	vector<int> dp(T+1);
	for(int i=1;i<=N;i++)
	{
		for(int j=T;j>=n[i].t;j--)
		{
			dp[j]=max({dp[j],dp[j-n[i].t]+n[i].a-n[i].d*j});
		}
	}
	cout<<*max_element(dp.begin(),dp.end());
}

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 1384K, 提交时间: 2020-02-17 18:02:48

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e6+1;
struct node{
	LL ms,pe,re; 
	bool operator<(node a){
		return pe*1.0/re>a.pe*1.0/a.re;
	}
}p[51];
LL dp[N];
int main(){
	int n,T;
	cin>>n>>T;
	for(int i=1;i<=n;++i)cin>>p[i].ms;
	for(int i=1;i<=n;++i)cin>>p[i].pe;
	for(int i=1;i<=n;++i)cin>>p[i].re;
	sort(p+1,p+n+1);
	for(int i=1;i<=n;++i){
		for(int j=T;j>=p[i].re;--j){
			dp[j]=max(dp[j-p[i].re]+p[i].ms-j*p[i].pe,dp[j]);
		}
	}
	cout<<*max_element(dp+1,dp+1+T)<<endl;
	return 0;
} 

C++(clang++ 11.0.1) 解法, 执行用时: 12ms, 内存消耗: 1244K, 提交时间: 2022-10-04 18:58:20

#include <bits/stdc++.h>
#define int long long
using namespace std;
class node {
	public:
		int m,s,t;
		inline const bool operator<(const node &x)const{
			return s*t+x.s*(x.t+t)<x.s*x.t+s*(t+x.t);
		}
} a[55];
int f[100005];
int n,t;
signed main() {
	int i,j;
	cin>>n>>t;
	for( i=1; i<=n; ++i)	cin>>a[i].m;
	for(i=1; i<=n;++i)cin>>a[i].s;
	for( i=1; i<=n; ++i)cin>>a[i].t;
	long long ans=0;
	sort(a+1,a+n+1);
	for(i=1; i<=n;   ++i)
		for(j=t; j>=a[i].t; --j)
			ans=max(f[j]=max(f[j],f[j-a[i].t]+a[i].m-a[i].s*j),ans);
	printf("%lld",ans);
}

pypy3 解法, 执行用时: 378ms, 内存消耗: 41548K, 提交时间: 2022-04-27 17:05:41

n, T = list(map(int, input().split(' ')))
mp = list(map(int, input().split(' ')))
p = list(map(int, input().split(' ')))
t = list(map(int, input().split(' ')))
q = [(mp[i], p[i], t[i]) for i in range(n)]
q.sort(key = lambda x: x[1] / x[2], reverse=True)
dp = [0] * (T + 1)
for i in range(n):
    ndp = [0] * (T + 1)
    for j in range(T + 1):
        ndp[j] = max(ndp[j], dp[j])
        if j + q[i][2] <= T:
            ndp[j + q[i][2]] = max(ndp[j + q[i][2]], dp[j] + q[i][0] - (j + q[i][2]) * q[i][1])
    dp = ndp[:]
print(max(dp))