NC14704 美味菜肴

题目地址：

https://ac.nowcoder.com/acm/problem/14704

基本思路：

这题我们考虑01背包,但是由于选择的时间先后会影响结果,所以我们要根据谁先选择更优做一个贪心,我们先考虑两个菜肴i和j,如果先选择i再选择j那么结果为 $a_{i} + b_{i}*c_{i} + ( a_{j} - b_{j} * (c_{i}+c_{j}) )$ 如果先选择j再选择i那么为 $a_{j} + b_{j}*c_{j} + ( a_{i} - b_{i} * (c_{i}+c_{j}) )$ 我们联立不等式设第一种情况更优就能解出 $c_{i}*b_{j} < c_{j}*b_{i}$ 所以我们将菜肴根据 $图片说明$ 和 $图片说明$ 的大小做一个排序再01背包就行了。

同时注意题目最后备注了：最大总美味值可能为负。也就是所我们不能一个菜肴都不做,这点感觉题目没有说清楚,所以注意负数情况和不要统计一个菜都不做的情况。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

struct Ndoe{
  int a,b,c;
  bool operator < (const Ndoe &no) const{
    return c * no.b < no.c * b;//按照谁先更优排序;
  }
}arr[100];
int n,m,T,t;
int dp[1000010];
map<int,int> memo;
int x,y,z;
signed main() {
  IO;
  cin >> n >> m >> T;
  rep(i,1,n){
    cin >> t;
    memo[i] = t;
  }
  rep(i,1,m){
    cin >> x >> y >> z;//这个输入顺序也有点奇怪,注意一下;
    arr[i] = {y,memo[x],z};
  }
  sort(arr+1,arr+1+m);

  mset(dp,-INF);//因为会有负数情况设为-INF;
  dp[0] = 0;
  rep(i,1,m){//01背包部分;
    for(int j = T ;j >= arr[i].c ; j--){
      dp[j] = max(dp[j],dp[j - arr[i].c] + arr[i].a - j * arr[i].b);
    }
  }
  int ans = -INF;
  rep(i,1,T) ans = max(ans,dp[i]);//统计从1开始;
  cout << ans << '\n';
  return 0;
}