solution
贪心+dp。
做这个题我们需要处理两个问题。第一个是如何确定这些菜的顺序,第二个是确定了菜的顺序之后如何计算答案。
先来确定菜的顺序。仔细观察之后,发现其实这个问题贪心思路和“国王的游戏”一样。如果只考虑两种菜。我们如果让在前,那么选这两种菜的答案就是,否则就是。发现都有,所以我们按照后面那一项排序,也就是,如果大于就让在前,否则让在前。
这样一遍就解决了第一个问题。然后就是第二个问题,用表示前种菜,用了的时间最大的收益。这就是一个简单的01背包了。
因为空间不够,所以要滚动数组或者压掉第一维。
code
/* * @Author: wxyww * @Date: 2020-04-27 11:11:24 * @Last Modified time: 2020-04-27 11:37:50 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 1000010; #define int ll ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } struct node { ll a,b,c; }a[N]; bool cmp(const node &A,const node &B) { return A.c * B.b < B.c * A.b; } ll tmp[N]; ll f[N]; signed main() { int n = read(),m = read(),T = read(); for(int i = 1;i <= n;++i) tmp[i] = read(); for(int i = 1;i <= m;++i) { a[i].b = tmp[read()];a[i].a = read(); a[i].c = read(); } sort(a + 1,a + m + 1,cmp); memset(f,-0x3f,sizeof(f)); f[0] = 0; for(int i = 1;i <= m;++i) { for(int j = T;j >= a[i].c;--j) { f[j] = max(f[j],f[j - a[i].c] + a[i].a - j * a[i].b); } } ll ans = -1e16; for(int i = 1;i <= T;++i) ans = max(ans,f[i]); cout<<ans<<endl; return 0; }