题解 P4377 【[USACO18OPEN]Talent Show G】

constexpr · 2021-07-04 11:45:36 · 个人记录

这里给出一种 O(nW) 的贪心+背包做法。

因为要求比值最大值，故考虑使用背包。定义 f_i 为总重为 i 的队伍才艺值总和的最大值 (i < W)。

首先将这 n 头奶牛以 t_i \div w_i 降序排序。

显然，对于 \forall j > k，由前 k 头牛中一些牛组成的队伍才艺与重量的比值 ans \geq t_j \div w_j。

由此可见，排序之后，在前 k 头牛已经组成符合要求的队伍中，对于 \forall j > k，再加入第 j 头牛不会让答案增加。

所以，当前 k 头牛中一些牛已经组成符合要求的队伍时，无需进行状态的转移，直接统计答案。

对于第 i 头奶牛，我们逆序枚举 j：

• 当 j+w_i \geq W 时，ans=\max(ans,(f_j+t_i) \div (j+w_i))
• 当 j+w_i < W 时，f_{j+w_i}=\max(f_{j+w_i},f_j+t_i)

最后的 ans即为答案。注意要乘上 1000。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
int n,s,w,t,ans,f[1010];
struct cow{
    int w,t;
}arr[1010];
int max(int x,int y){
    return x>y?x:y;
}
bool cmp(cow x,cow y){
    return x.t*y.w>y.t*x.w;
}
int main(){
    scanf("%d %d",&n,&s);
    memset(f,0x80,sizeof(f));f[0]=0;
    for(register int i=0;i<n;i++)scanf("%d %d",&arr[i].w,&arr[i].t);
    std::sort(arr,arr+n,cmp);
    for(register int i=0;i<n;i++){
        for(register int j=s-1;j>=0;j--){
            if(j+arr[i].w>=s)ans=max(ans,(f[j]+arr[i].t)*1000/(j+arr[i].w));
            else f[j+arr[i].w]=max(f[j+arr[i].w],f[j]+arr[i].t);
        }
    }
    printf("%d",ans);
    return 0;
}