一共有 n 件食材,每件食材有三个属性,$a[i],b[i] 和 c[i]$,如果在 t 时刻完成第 $i$样食材则得到 $ai-t*bi$的美味指数,用第 $i$件食材做饭要花去 $c[i]$的时间。
众所周知,gw 的厨艺不怎么样,所以他需要你设计烹调方案使得美味指数最大。


一开始,我抱着试试看的心态打了一个全裸的 01 背包(不要想歪)。结果,听取 WA 声一片,30 分。
于是我们静下心来,仔细想想。
发现 01 背包的错误在于 $b[i]$,于是我们开始了漫长的倒过程。
如果是 i 先做,可得美味指数为:$a[i]−b[i]∗(t+c[i])+a[j]−b[j]∗(t+c[i]+c[j])$
如果是 j 先做,可得美味指数为:$a[j]−b[j]∗(t+c[j])+a[i]−b[i]∗(t+c[i]+c[j])$
设:i 先做比 j 先做的结果大。
则:$a[i]−b[i]∗(t+c[i])+a[j]−b[j]∗(t+c[i]+c[j])>a[j]−b[j]∗(t+c[j])+a[i]−b[i]∗(t+c[i]+c[j])$
那么,等式两边同时减去 $a[i]+a[j]$, 得:$−b[i]∗(t+c[i])−b[j]∗(t+c[i]+c[j])>−b[j]∗(t+c[j])+−b[i]∗(t+c[i]+c[j])$
展开,得:$-b[i]t-b[i]c[i]-b[j]t-b[j]c[i]-b[j]c[j]>-b[j]t-b[j]c[j]-b[i]t-b[i]c[j]-b[i]c[i] $
化简,得:$−b[j]∗c[i]>−b[i]∗c[j] $
最后,按上式排序之后就是常规操作了。
p.s.:一个小细节要开 long long!


code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[1000001],n,m,ans;
struct node {
    int a,b,c;
    friend inline bool operator < (const node &rhs,const node &rs) {
        return rhs.b*rs.c > rhs.c*rs.b; 
    }
}pre[1000001];
signed main() {
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i].a;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i].b;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i].c;
    }
    sort(pre+1,pre+1+n);
    for (int i=1;i<=n;i++) {
        for (int j=m;j>=pre[i].c;j--) {
            f[j]=max(f[j],f[j-pre[i].c]+(pre[i].a-j*pre[i].b));
        }
    }
    for (int i=1;i<=m;i++) {
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}
分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注