小明是個大廚，早上起來他開始一天的作業，他所在的餐廳每天早上都會買好n件食材（每種食材的數量可以視為無限），小明從到達餐廳開始就連續作業T時間，每道菜肴的制作需要特定的一種食材以及一段時間，但是食材一旦放久就不新鮮了，菜的美味值會降低，第i道菜肴有三個屬性ai，bi，ci，ai是該菜肴的美味值，bi是該菜肴所選食材不新鮮的速率，如果在第t時刻完成第i道菜則美味值為：ai-t*bi，完成這道菜需要ci的時間，小明希望在這T時間內能做出菜肴使得總美味值最大，所以小明求助于你，
輸入描述:
第1行輸入三個整數n，m，T，分別代表食材種類，菜肴種類和作業時間，
第2行輸入n個整數bi，代表第i個食材不新鮮的速率，
第3-n+2行，每行輸入三個整數j，ai，ci，分別代表第i道菜肴需要的食材編號，菜肴的美味值，完成時間，
資料保證：0<n,m≤50，0<j≤n，其他值均<106，美味值必須通過完整做出菜肴得到，資料保證在規定時間內至少能完整做出1道菜肴，
輸出描述:
輸出一行，一個整數，表示最大總美味值，
示例1
輸入
1 1 74
2
1 502 47
輸出
408
示例2
輸入
2 2 10
2 1
1 100 8
2 50 3
輸出
84
備注:
最大總美味值可能為負，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1<<20],b[1<<20];
struct node
{
ll b,a,c;
}a[1<<20];
int 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>>a[i].b>>a[i].a>>a[i].c, a[i].b=b[a[i].b];
sort(a+1,a+1+m,[](node x,node y)
{
return x.b*y.c>x.c*y.b;
});
for(int i=1;i<=T;i++) dp[i]=-1e18;
for(int i=1;i<=m;i++)
for(int l=T;l>=a[i].c;l--)
dp[l]=max(dp[l],dp[l-a[i].c]+a[i].a-l*a[i].b);
ll ans=-1e18;
for(int i=1;i<=T;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/267116.html
標籤：其他
上一篇：計算機網路基礎之物理層功能與協議
下一篇：RTTHREAD軟體包目錄