牛客—codeforces(贪心+01背包)

题目：codeforces
来自大佬的分析：
这道题还是有点意思的，由于本题的做题选择会影响最后的得分，所以需要知道每一道题的优先级。下面我们来推导一下，如何来选择做题顺序，即每一道题的优先级。
对于两道题t1,t2来说，有两种做题顺序，如下图的C12,C21,我们定义P1为t1的每分钟减小的分数，T1为做题需要的时间
两道题的初始总分数为sum(最大分数之和）
则
得分C12=sum-T1P1-(T1+T2)P2;
得分C12=sum-T2P2-(T1+T2)P1;
则 C12-C21=T2P1-T1P2
要判断两道题的大小，这上式同时除T1*T2的P1/T1-P2/T2 这样我们就发现了优先级函数为P/T即每分钟减小分数除需要的做题时间
排好序之后，进行01背包的dp算法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[52][100002],n,t,Max=-1;
typedef struct Node{
	ll v,c,w;
}Node;
Node a[52];
bool cmp(Node &A,Node &B){
	//return 1.0*A.c/A.w>1.0*B.c/B.w;
	return A.c*B.w>B.c*A.w;
}
int main(){
	
	scanf("%d %d",&n,&t);
	for(int i=0;i<n;i++) scanf("%lld",&a[i].v);
	for(int i=0;i<n;i++) scanf("%lld",&a[i].c);
	for(int i=0;i<n;i++) scanf("%lld",&a[i].w);
	
     sort(a,a+n,cmp);
     for(int i=0;i<n;i++){
     	for(int j=0;j<=t;j++){
     		if(a[i].w>j) dp[i+1][j]=dp[i][j];
     		else dp[i+1][j]=max(dp[i][j],dp[i][j-a[i].w]+a[i].v-j*a[i].c);
     		Max=max(Max,dp[i+1][j]);
		 }
	 }
	printf("%lld\n",Max);
	
	
	
	return 0;
}