原题链接：https://www.luogu.org/problem/show?pid=1417

 

这个题虽然是DP。但是也只不过是01背包的变种，但是因为和顺序有了关系，所以加了一点点贪心。

主要来说一下贪心的策略。

对于每一组 x<y 都有 x.c/x.b<y.c/y.b。

排在后面的一定是因为c太大或者b太小，c大会浪费时间，b小放在后面也不会有什么问题。（这贪心也蛮玄学的。。。）

这样就可以减少因为做饭时间太长而导致的美味度减少。为了排除精度问题，要改为交叉相乘的写法。

按贪心排好序后，就像一个01背包了，稍微注意一下题意就好。

还有值得说的是，这个题极限计算量100000*100000，会爆int，所以要用longlong，这让我想起来对面的dalao在模拟赛上因为这个问题被卡掉70分的经历。。。

 

#include
     
      #include
      
       using namespace std;int t,n;long long f[100005],ans;struct th{    long long a,b,c;}p[55];bool cmp(th x,th y){    return ((x.c*y.b)<(x.b*y.c));}int main(){//    freopen("testdata.in","r",stdin);    scanf("%d %d",&t,&n);    for(int i=1;i<=n;i++) scanf("%lld",&p[i].a);    for(int i=1;i<=n;i++) scanf("%lld",&p[i].b);    for(int i=1;i<=n;i++) scanf("%lld",&p[i].c);    sort(p+1,p+n+1,cmp);    for(int i=1;i<=n;i++)    {        for(int j=t;j>=p[i].c;j--) f[j]=max(f[j],f[j-p[i].c]+p[i].a-j*p[i].b);    }     for(int i=0;i<=t;i++) ans=max(ans,f[i]);    printf("%lld",ans);    return 0;}