P4377 [USACO18OPEN] Talent Show G 题解

· · 题解

听说这题是分数规划的板子题，所以我用神犇 Konjac_HZX 的裸背包做法过了，时间复杂度十分优秀。

一种比较暴力的思想：我们直接做背包，f_{i,j} 表示前 i 个奶牛总重量为 j 下最大的才艺值，然后统计统计就可以了。

时间复杂度瓶颈是什么？我们发现总重量和可能很大，所以背包很慢。

有一个定理，俗话叫糖水定理，就是 \max(\dfrac a b,\dfrac c d)\geq \dfrac{a+c}{b+d}，这个东西的证明比较简单，用分数基本性质算一算就行了。

这给了我们什么启发呢？加上奶牛只会让比变小，当然你加上一个这个分数值比你目前方案的分数值大的奶牛（神仙牛）除外，但是这种情况我已经选择的奶牛为啥不选一些干掉换成这个神仙牛呢？你的身价是抬高了，但是神仙牛却自降身价了。这样在全局上是不优的，会被选择了神仙牛的方案比下去。

所以说我们在处理背包时，加到满足重量限制条件的时候就停止结算。

比如，当前重量为 x 的奶牛尝试用 f_{i-1,j} 更新 f_{i,j+x} 时发现 j+x\geq W，那么我们就直接结算这种可能，更新答案。

注意我们需要排序把比较轻的奶牛放在前面，不然大奶牛结算了，我们会没考虑到一些小奶牛填充空间，大奶牛加入结算的可能。

时间复杂度为 \mathcal O(nm)。

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const LL N=255;
const LL M=1005;
LL n,m,f[N][M],ans;
struct node
{
    LL a,b;
}a[N];
bool cmp(node x,node y)
{
    return x.a<y.a;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i].a,&a[i].b);
    }
    memset(f,-127,sizeof(f));
    f[0][0]=0;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j-a[i].a>=0)f[i][j]=max(f[i][j],f[i-1][j-a[i].a]+a[i].b);
            if(j+a[i].a>=m)ans=max(ans,(f[i-1][j]+a[i].b)*1000/(j+a[i].a));
        }
    }
    printf("%lld",ans);
}