解题报告 P1417 烹调方案

题目内容

P1417

大意：有 n 种食物，每种食物有 a_i，b_i，c_i 三个参数，定义 t 时刻烹饪完成食物时食物的美味度为 a_i-b_it，烹饪一个食物需要 c_i 时间，求 t 时间内能达到的最大美味度。

解题思路

如果不考虑 b 这个参数的话，他就是一个裸的 0-1 背包，但是由于 b 参数的存在，就需要考虑烹饪食物的顺序对结果的影响。下面进行推导：

设我们在比较两个相邻的食物 x 和 y，当前的时刻为 p，则如果先做 x 再做 y 的话总的美味度是

\begin{aligned}
&a_x-(c_x+p)b_x+a_y-(c_y+c_x+p)b_y\
=&a_x+a_y-b_xc_x-b_yc_y-b_yc_x-b_xp-by_p
\end{aligned}

反之如果先做 y 的话：

\begin{aligned}
&a_y-(c_y+p)b_y+a_x-(c_y+c_x+p)b_x\
=&a_x+a_y-b_xc_x-b_yc_y-b_xc_y-b_xp-by_p
\end{aligned}

假设现在需要先做 x 达到的美味程度最大，则

\begin{aligned}
a_x+a_y-b_xc_x-b_yc_y-b_yc_x-b_xp-by_p>&a_x+a_y-b_xc_x-b_yc_y-b_xc_y-b_xp-by_p\
b_yc_x>&b_xc_y
\end{aligned}

因此在背包之前需要先给食物进行排序，然后再背包。

然后可能炸 int，要上 long long

#include <cstdio>
#include <algorithm>
using std::sort;
using std::max;
typedef long long ll;

int n,t,f[100005];

struct food
{
    ll a,b,c;
}x[55];

bool cmp(food a,food b)
{
    return (ll)a.c*(ll)b.b<(ll)b.c*(ll)a.b;
}

int main()
{
    scanf("%d %d",&t,&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i].a);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i].b);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i].c);
    sort(x+1,x+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=t;j-x[i].c>=0;j--)
            f[j]=max((ll)f[j],f[j-x[i].c]+x[i].a-j*x[i].b);
    int ans=0;
    for(int i=1;i<=t;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}