题解 | #美味菜肴#

美味菜肴 (nowcoder.com)

被这题折磨了一天，呜呜呜

题意：给你n到菜，每道菜的美味度会随时间下降，告诉你下降速率，问在t时间内能够达到的最大的美味度是多少

思路：贪心+dp，我拿到就直接写01背包了，但是由于时间的因素导致每个时间下状态是会改变的，所以先进背包和后进背包是有区别的。比如：我只有两个物品，我先转移1再转移2最后会得到四个状态：0，1，2，1-2，先转移2再转移1会得到四个状态：0，1，2，2-1，由此可见，两个方法均没有考虑到所有的状态，而是以进入背包的顺序当作做菜的相对顺序来转移的，所以我们就需要一个预处理，优先考虑对答案价值大的菜品，即给所有的菜进行排序，那排序规则怎么定呢，这个其实就是一个简单的邻项交换法推导贪心公式的应用，详情见：贪心 - OI Wiki (oi-wiki.org)

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
struct node{
	int j,a,b,c;
};
node x[55];
int dp[1000011];
int b[55];
bool com(node a,node b){
	return a.c*b.b<a.b*b.c;
}

signed main()
{
	int n,m,t;
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=m;i++){
		cin>>x[i].j>>x[i].a>>x[i].c;
		x[i].b=b[x[i].j];
	}
	sort(x+1,x+m+1,com);
	for(int j=0;j<=t;j++){
		dp[j]=-INF;
	}
	dp[0]=0;
	int ans=-INF;
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			if(j-x[i].c>=0){
				dp[j]=max(dp[j],dp[j-x[i].c]+x[i].a-x[i].b*j);
				ans=max(dp[j],ans);
			}		
		}
	}
	cout<<ans<<endl;
}