Clearlove7loveyou @ 2018-12-22 10:39:28
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int t,n,ans;
int dp[100005];
struct node{
int a,b,t;
}meal[55];
int cmp(node a,node b){ return a.t*a.b<b.b*b.t;}
/*
a1-t1b1+a2-(t1+t2)b2 ①
a2-t2b2+a1-(t1+t2)b1 ② ①-②
*/
int main(){
scanf("%d%d",&t,&n);
for(int i=1;i<=n;i++){ scanf("%d",&meal[i].a);}
for(int i=1;i<=n;i++){ scanf("%d",&meal[i].b);}
for(int i=1;i<=n;i++){ scanf("%d",&meal[i].t);}
sort(meal+1,meal+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=t;j>=meal[i].t;j--){
dp[j]=max(dp[j],dp[j-meal[i].t]+meal[i].a-j*meal[i].b);
// ans=max(ans,dp[j]);
}
}
for(int i=1;i<=t;i++){
ans=max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}
by 寒月·惊鸿 @ 2019-06-02 21:22:32
应该是
const bool cmp(node& a,node& b){
return a.t*a.b < b.b*b.t;
}
吧...