「luogu1417」烹调方案

题目链接 ：https://www.luogu.org/problemnew/show/P1417

直接背包 ->  30'

考虑直接背包的问题：在DP时第i种食材比第j种食材更优，但由于j<i导致第j种食材先被决策到，故 GG

显然：当i，j满足  f[t]+a[i]-b[i]*(c[i]+t) > f[t]+a[j]-b[j]*(c[j]+t) <=> b[i]*c[i] < b[j]*c[j]  第i种更优；

 //Author : 15owzLy1

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #define lson tl, mid, rt<<1

 #define rson mid+1, tr, rt<<1|1

 #define pb(__) push_back(__)

 #define fr() front()

 #define bg() begin()

 #define it iterator

 #define INF 2100000000

 typedef long long ll;

 typedef double db;

 template<class T>inline void get_max(T &_, T __) { _=_>__?_:__; }

 template<class T>inline void get_min(T &_, T __) { _=_<__?_:__; }

 template<class T>inline void Swap(T &_, T &__) { T ___=_;_=__;__=___; }

 template<class T>inline T abs(T _) { return _>?_:-_; }

 template<typename T>inline void read(T &_) {

     _=;bool __=;char ___=getchar();

     while(___<''||___>''){__|=(___=='-');___=getchar();}

     while(___>=''&&___<=''){_=(_<<)+(_<<)+(___^);___=getchar();}

     _=__?-_:_;

 }

 const int N = , M = ;

 struct node {

     int a, b, c;

     bool operator < (const node x) const {

         return 1ll*this->c*x.b < 1ll*this->b*x.c;

     }

 }dish[N];

 int T, n;

 ll res, f[M];

 int main() {

         //freopen(".in","r",stdin);

     //freopen(".out","w",stdout);

     read(T), read(n);

     for(int i=;i<=n;i++) read(dish[i].a);

     for(int j=;j<=n;j++) read(dish[j].b);

     for(int k=;k<=n;k++) read(dish[k].c);

     std::sort(dish+, dish++n);

     for(int i=;i<=n;i++)

         for(int j=T;j>=dish[i].c;j--) {

             get_max(f[j], f[j-dish[i].c]+1ll*dish[i].a-1ll*j*dish[i].b);

             get_max(res, f[j]);

         }

     printf("%lld\n", res);

     fclose(stdin);

     fclose(stdout);

     return ;

 }