洛谷P2340 奶牛会展

@Pelom  September 26, 2019

题意

有$N$头奶牛,每头奶牛都有智商$S$和情商$F$,要从中选出一些奶牛,要求情商总和和智商总和都不能为负,求情商和智商最大总和

数据范围:$1 \le N \le 400,-1000 \le S,F \le 1000$

题解

选或不选,很像$0/1$背包,于是将其中一个值作为背包容量,另一个作为价值(例如此处将$S$作为容量,$F$作为价值),则可用$f[i]$表示$S=i$时$F$的最大值,在$i$所有的取值中求$max(i+f[i])$即为答案
但需要注意的是,本题有负数,而我们依赖数组下标储存$S$,不可以出现负数,于是考虑使用映射或将数组偏移,偏移的值可定为$1000 \times 400=400000$,在涉及到下标的地方均需注意处理
不仅如此,因为负数的转移方向与正数相反(正数从小的容量转移而来,而负数应从大的容量转移而来),需注意区分

代码:

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
const int N=400+10;
const int M=400000;
int n;
int s[N],f[N];
int dp[(M<<1)+10];
int ans;
template <typename T>
inline T Max(T a,T b){
    return a>b?a:b;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&s[i],&f[i]);
    memset(dp,0xc0,sizeof(dp));
    dp[M]=0;
    for(int i=1;i<=n;i++)
        if(s[i]>=0)
            for(int j=(M<<1);j>=s[i];j--)
                dp[j]=Max(dp[j],dp[j-s[i]]+f[i]);
        else
            for(int j=0;j<=(M<<1)+s[i];j++)
                dp[j]=Max(dp[j],dp[j-s[i]]+f[i]);
    for(int i=M;i<=(M<<1);i++)
            if(dp[i]>=0)
                ans=Max(ans,i+dp[i]-M);
    printf("%d",ans);
    return 0;
}

添加新评论