【每日一题】 美味菜肴 题解

Solution

经典0-1背包问题, 题目的输入描述有点问题

第3-n+2行 -> 第 3 - m + 2 行

直接做背包是错的, 因为这里多了一个时间的限制, 价值随着时间而变化
同样是背包但是先进背包和后进背包有区别
因此需要考虑贪心策略下背包
对于两个物体 , , 先取 物体比先取 物体优
当且仅当
化简一下就是
排序后进行背包就行了
注意题目要求必须至少做一道菜, 这里有个人尽皆知的小技巧
把 数组赋值为无穷小, , 这样可以保证 满足至少取一个

Code

/*
  autor: Kurisu
  2020年4月30日08:59:23
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 2e5 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;
ll b[N];
ll dp[N];
struct node {
  ll id, a, c;
  bool operator < (const node &s) const {
    return b[s.id] * c < b[id] * s.c;
  }
}d[N];
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 >> d[i].id >> d[i].a >> d[i].c;
  } 
  sort(d + 1, d + 1 + m);
  memset(dp, -0x3f, sizeof(dp));
  dp[0] = 0;
  ll ans = -1e18;
  for(int i = 1; i <= m; i++) {
    for(int j = t; j >= d[i].c; j--) {
      dp[j] = max(dp[j], dp[j - d[i].c] + d[i].a - b[d[i].id] * j);
      ans = max(ans, dp[j]);
    }
  }
  cout << ans << "\n";
  return 0;
}