题解 | #codeforces#

基本是其他大佬的思路 但cmp方法 按自己的想法推测。 感谢大佬提供的01背包思路。

#include<algorithm>
#include<cmath>
using namespace std;
struct point{
int mp,pm,rt;
}a[52];
long long dp[100005];
struct cmp{
      bool operator()(const point&a,const point&b) const{//两条方式均可
          return a.rt*1.0/a.pm < b.rt*1.0/b.pm;
//           return a.pm*1.0/a.rt >b.pm*1.0/b.rt;
      }  
};
int n,t;
int main(){
    cin >> n>>t;
    for(int i =0;i<n;i++) cin>>a[i].mp;
    for(int i =0;i<n;i++) cin>>a[i].pm;
    for(int i =0;i<n;i++) cin>>a[i].rt;
    sort(a,a+n,cmp());
    long long  ans = 0;
    for(int i = 0;i<n;i++){
        for(int j= t;j>=a[i].rt;j--){
            dp[j]=max(dp[j],dp[j-a[i].rt]+a[i].mp-a[i].pm*j);//
            ans=max(ans,dp[j]);
        }
    }
    cout<< ans;
    return 0;
}

//https://blog.csdn.net/qq_18343569/article/details/52061220

22~27行代码是01背包的空间优化，可以参考链接中查看。